1. Westrick: randomness and rotations of the unit circle
The following result was obtained at the computability retreat at Research Centre Coromandel in February. It started through discussions between Adam Day, Andre Nies, Dan Turetsky and Brown Westrick.
\vsp
Let P⊆[0,1] be a Π10 class.
\begin{thm}
Let X∈MLR. Let k∈N.
1. There is a rational number q=0 such that for all i≤k, X+qi∈P.
2. Let α be a computable irrational number.
There is an integer n=0 such that for all i≤k, (X+αnimod1)∈P.
\end{thm}
\begin{proof}
Both (1) and (2) are proved by the same method. Dynamically construct a Solovay test as follows. Put the empty string ⟨⟩ in the test. Then for any σ that has been placed in the test, let rσ be a rational number (for (1)) or let nσ>0 be an integer (for (2)) such that \bc 2k+32−∣σ∣<rσ,(αnσmod1)<2k+22−∣σ∣. \ec These bounds are chosen so that for every z∈[σ], z+krσ∈[σ] or z−krσ∈[σ]. Let Us denote the complement of P as seen at stage s. We will enumerate τ into the test at stage s if we see the following occur:
1. σ≺τ,
2. τ is incomparable with any τ′ which has already entered the test on the basis of this same σ
3. [τ]∩Us=∅
4. For some integer i∈[−k,k], [τ]+irσ⊆[σ]∩Us.
The point is to enumerate [τ] if its potential ±rσk-recurrence inside [σ] is invalidated. For (2), replace rσ everywhere with αnσmod1.
The test catches any z∈P which fails to k-recur for all r∈Q∖{0} (resp. for all αn with n∈Z∖{0}). We need to show it is a Solovay test.
We show that for every σ in the test, the total measure of all τ added to the test as a result of σ is at most 2k+32k+2μ[σ]. So if the depth of τ is the number of initial segments that τ has in the test, then μ(∪{[τ]:τ of depth d})≤(2k+32k+2)d, so this will suffice to show that the total measure of the test is finite.
When σ is first put in the test, [σ] is disjoint from Us. When first ρ enters Us with σ≺ρ, we can consider [σ] as being divided into two parts, both invariant under addition of rσ: C={z∈[σ]:z+irσ∈[ρ] for some i∈Z}, and its complement. All z whose initial segments could potentially be enumerated as a result of ρ are contained in C. Also [ρ]⊆C, but nothing comparable with ρ will be enumerated. By the choice of rσ, μCμ[ρ]≤2k+31. Therefore, the measure added to the test as a result of the addition of ρ, and as a result of the addition of any future ρ′ with [ρ′]⊆C, is bounded by 2k+32k+2μC.
The remaining set [σ]∖C is currently untouched but may in the future be seen to intersect the complement of P. When that happens, we apply the same reasoning inside of [σ]∖C, partitioning it into two invariant pieces and arguing that one piece remains untouched, while the other can never contribute more than 2k+32k+2 of its measure to the test. Continuing in this way, we get the desired bound on the measure the test uses in response to σ.
\end{proof}
2. Nies: alternative proof of Thm.\ \ref{thm:multiple recurrence
(1)}
The case k=1 of the theorem can be derived from a result of Figueira et al.\ 14; also see \cite[3.3.7]{Nies:book}. That theorem of 14 says that if X is not autoreducible, then there is a bit position n such that the bit n is indifferent for X with respect to P, which means that we can change X at n and remain in P. This change corresponds to adding or subtracting the rational 2−n.
Now let us obtain an arithmetical progression namely X+qi∈P for i<k/2 (for technical reasons).
At first we work with Z∈kω. Extending the case of k=2, we say that Z is auto-reducible if there is a reduction procedure Φ such that ΦZ(n)=Z(n) for each n, and the computation ΦZ(n) only queries the oracle at values other than n. As before, one checks that a ML-random sequence Z is not auto-reducible. We say that position n is indifferent for Z with respect to a Π10 class P⊆kω if we can change Z at n to any value <k and remain in P.
\begin{prop} Let Q⊆kω be a Π10 class. If Z∈Q is not autoreducible, then there is a position n such that the bit n is indifferent for Z with respect to Q. \end{prop}
\begin{proof} A straightforward extension of the argument for k=2. If there is no such position, given input n the reduction Φ searches for a stage s and i<k such that Z, with position n changed to value i, is not in Q, and once found, output this i.
\end{proof}
To obtain the arithmetical progression assume that k=2r for r∈N. Given Π10 class P⊆2N and ML-random X∈P , let Q, Z be the class/sequence rewritten using the alphabet 0,…,k−1. That is, the block bits of X in positions nr…(n+1)r−1 corresponds the symbol of Z in position n. If n is indifferent for Z in Q, then we have an arithmetical progression X+qi∈P, where i<k/2, q=±2−rn.
The following is work of Greenberg, Miller, Nies and Turetsky at RCC in Feb.\ 2015, and in Wellington slightly later. For background on cost functions see 30. In the following all cost functions satisfy the limit condition limx\cost(x)=0.
\begin{definition}[3] Let \cost be a cost function. A descending sequence \seq{V_n} of uniformly c.e.\ open sets is a \cost-bounded test if λ(Vn)=O(\limcost(n)) for all n. \end{definition}
We think of each Vn as an approximation for Y∈⋂kVk. Being in ⋂nVn can be viewed as a new sense of obeying \cost that makes sense for ML-random sets.
\begin{lemma} Suppose aY fails a \cost-bounded test ⋂nVn where a∈{0,1}. Then Y fails a \cost-bounded test. \end{lemma}
\begin{proof} We may suppose a=0 and X∈Vn implies X(0)=0. Since λT(Vn)≤2λVn where T is the usual shift operator on Cantor space, (T(Vn)i)i∈N is also a \cost-bounded test. Clearly Y fails it. \end{proof}
The basic motivating result is a generalisation in terms of cost functions of a fact of Hirschfeldt and Miller.
\begin{prop} If A⊨\cost and Y is a ML-random captured by a \cost-bounded test, then A≤TY. \end{prop}
The most powerful kind of set obeying a given cost function
The following is the central definition for this entry: given \cost, we consider sets A such that the converse implication holds as well.
\begin{definition} Let \cost be a cost function and A be a Δ20 set. We say that A is smart for \cost if A⊨\cost and for each ML-random set Y,
\begin{center} Y is captured by a \cost-bounded test ⇔A≤TY. \end{center} \end{definition}
Informally, if A is smart for \cost then A is as complex as possible among the sets obeying \cost, in the sense that the only random sets Y above A are the ones that have to be there because A obeys the cost function that puts it below Y anyway.
\begin{theorem} Let \cost be a cost function with \cost→\costΩ. Some c.e.\ set A is smart for \cost. \end{theorem}
\begin{proof} Recall Υ is a ``universal" Turing functional in the sense that Υ(0e1\concX)=Φe(X) for each X,e. We build A and a \cost-test \seq{\+ U_k} capturing any ML-random Y such that A=ΥY. This suffices for the theorem by Lemma~ ?.
Since 2−x≤×Ω−Ωx, we may assume that \cost(x,s)≥2−x for x≤s.
As in 3, during the construction of A we build a global ``error set":
All all stages s we will have
\[ \tag{⋄} \leb \+ U_{k,s} \le \cost(k,s) + \leb ( \+ E_{s+1} - \+ E_k). \]
So since λ(\+E−\+Ek)≤×\costΩ(k) and \costΩ(k)≤×\limcost(k), the test \seq{\+ U_k} is indeed a \cost-test.
We reserve the interval Ik=[2k,2k+1) for ensuring (⋄). The construction of \+Uk is as follows.
At stage s>k, let x=min(Ik−As−1). Let
\[ \+ U_{k,s} = \bigcup_{t⋄) threatens to fail at s, namely λ\+Uk,s>\cost(k,s)+λ(\+Es−\+Ek), put x into As+1. This causes \+Uk,s to go into \+Es+1.
First we verify that x always exists, that is, we enumerate at most 2k times for \+Uk. If we do this at stage s, λ\+Uk,s>2−k+λ(\+Es−\+Ek). Since \+Uk,s∩\+Ek=∅ by definition, and \+Uk,s⊆\+Es+1, it follows that λ(\+Es+1−\+Es)>2−k. Since λ\+E≤1, this can happen at most 2k times.
In particular, if A=ΥZ then Z∈⋂k\+Uk.
It remains to verify that A⊨\cost. If we enumerate x for \+Uk at stage s then
\[ \leb (\+ U_{k,s} - \+ E_s) = \leb (\+ U_{k,s} - (\+ E_s - \+ E_k) ) \ge \leb (\+ U_{k,s} ) - \leb(\+ E_s - \+ E_k) > \cost(k,s ) \ge \cost (x,s). \] Since \+Uk,s−\+Es⊆\+Es+1−\+Es, we see that \cost(x,s)<λ(\+Es+1−\+Es). This implies that the total cost of the enumeration of A is at most 1.
\end{proof}
ML-reducibility
\begin{definition}[3] For K-trivial sets A and B, we write B≤MLA if A≤TY implies B≤TY for any ML-random set Y.
\end{definition}
Clearly, ≤T implies ≤ML. The ML-degrees form an upper semilattice where the least upper bound of K-trivial sets C and D is given by the K-trivial set C⊕D.
\begin{definition} Let \cost be a cost function and A be a Δ20 set. We say that A is ML-complete for \cost if A⊨\cost, and ∀B[B⊨\cost⇒B≤MLA]. \end{definition}
\begin{cor} A is smart for \cost⇔A is ML-complete for \cost. \end{cor}
\begin{proof}
⇒: Suppose A≤TY for ML-random Y. Then some \cost-bounded test captures Y. If B⊨\cost, then B≤TY by the basic fact~ ?. Thus B≤MLA as required.
\noindent ⇐: By Theorem~ ? let A be smart for \cost. Suppose A≤TY for ML-random Y; we want to show that Y is captured by a \cost-bounded test. Since A is ML-complete for \cost we have A≤MLA, so A≤TY, so Y is captured by a \cost-bounded test as required.
\end{proof}
In particular, the ML-degree of a smart set A for \cost is uniquely determined by \cost. On the other hand, for each low c.e.\ set A there is a c.e.\ set B≤TA such that B⊨\cost \cite[5.3.22]{Nies:book}. If A is smart for \cost, then A⊕B is also smart for \cost. As each K-trivial is low, the Turing degree of a set A that is smart for \cost is not uniquely determined by \cost.
\begin{question} Given \cost can we build a smart for \cost set A that is cappable? Can we even have two smart for \cost sets that form a minimal pair? \end{question}
The strongest cost function obeyed by a given set
Given c.e.\ K-trivial A we will define a c.f.\ \costA with A⊨\costA such that every random computing A is captured by a \costA test. (In other words, A is smart for cA.) However, \costA may not be a very natural cost function. We build a K-trivial A such that the class of sets obeying \costA is not closed downward under ≤T, and in fact not even the shift T(A) obeys \costA.
As before Υ denotes a ``universal" Turing functional. Given a c.e.\ K-trivial set A, fix a c.e.\ approximation \seq{A_s} \models \cost_\Omega. We let
\[ \cost_A(x,s) = \leb \bigcup_{x\le t< s} \{ Y \colon A_t \uhr {x+1} \preceq \Upsilon_t^Y \}.\]
\begin{prop} (i) A⊨\costA. (ii) Suppose \cost is a cost function such that A⊨\cost. Then \costA→\cost. In particular, \costA→\costΩ. \end{prop}
\begin{proof} (i) We show that the fixed approximation \seq{A_s} \models \cost_A. Define the left-c.e.\ ``error real'' by:
\[
\epsilon_s = \leb\{Y : \exists n [\Upsilon^Y_s(n)\converge=0 \wedge A_s(n) =1]\}
\]
Note that if x∈As−As−1, then \costA(x,s)≤ϵs−ϵx=\costϵ(x,s). So \cost_A\seq{A_s} \le \cost_\epsilon\seq{A_s}. Since \costΩ→\costϵ, and \seq{A_s} \models \cost_\Omega, it follows that \seq{A_s} \models \cost_A.
(ii) By multiplying by a constant, we may assume that \cost(0)<1/2. Fix a computable speed-up f such that \cost\seq{A_{f(s)}} \lt 1/2. Define a Turing functional Ψ such that at every stage f(s), λ{Y:Af(s)↾x+1≺Ψf(s)Y}=\cost(x,s). By a simple argument, the measure of the error-set \+E for this functional will be \cost\seq{A_{f(s)}} \lt 1/2, so this construction may proceed.
Fix e with Φe=Ψ. Then \limcostA(x)≥2−(e+1)\limcost(x).
\end{proof}
Recall that T(A) is the shift of A.
\begin{thm}
For each cost function \dost, there is a cost function \cost≥\dost and a c.e.\ set A such that A⊨\cost and T(A)⊨\cost. \end{thm}
Since \costA→\cost, this shows that T(A)⊨\costA.
\begin{proof} We fix a listing \seq{\Phi_e} of all (possibly partial) computable enumerations \seq{B_t}, where Bt≃DΦe(t) and DΦe(t)⊆DΦe(t+1) if defined.
We may assume \dost(s−1,s)≥2−s. We define \cost(x,s) so that \cost(x,s)≥\dost(x,s) for each x,s. At a stage x of the construction we may also declare that \cost(x−1,x)≥α, which by monotonicity entails that \cost(y,s)≥α for each y<x and s≥x.
We meet the requirements
\[R_e \colon \, T(A) = \bigcup_t D_{\Phi_e(t)} \RA \cost \seq {\Phi_e} \ge 1. \]
The strategy for Re tries to ensure \limcost(x−1) is large and \limcost(x) is small for sufficiently many x. In that case Re can put x into A for the small cost, while the opponent's enumeration \seq{\Phi_e} of T(A) has to deal with the large cost. One problems in implementing this idea is the timing as we will of Φe(u) for a stage u only at a stage s much larger than u. Also we always have \cost(x,s)≥\dost(x,s), so once we discover that the enumeration of x would help because \seq{\Phi_e} caught up sufficiently much, it may be that the enumeration of x has become too expensive for Re. Similar to the usual construction of a set obeying \dost, in this case we simply pick a new x. Since \dost has the limit condition, eventually we will always be able to keep x.
At a stage s>0 let s\init(e) be the greatest stage t<s such that t=0 or Re has been initialised at t. If by stage s the strategy for Re has been initialised for b times it can spend a \cost-cost of 2−b−e in enumerating A. It is also allowed to raise \cost(x,s) to 2−\sinit(e).
The e-expansionary stages are the ones at which \seq {\Phi_e} catches up with T(A). We declare 0 as e-expansionary. A stage s>0 is e-expansionary if for the largest e-expansionary stage t<s, we have that T(As)↾t+2=Φe,s(u)↾t+2 where u is largest such that Φe,s(u) is defined and u>t.
\noindent Strategy for Re. Write α=2−\sinit(e). A rational parameter γe∈[0,1] measures progress of Re. We set γe to 0 when Re is initialised.
At e-expansionary stage s, if γe≤1 do the following. Initialize lower priority requirements. Declare that \cost(s−1,s+1)≥α. (So for Φe, changing at s−1 will be expensive after stage s.)
Let x<s be the last e-expansionary stage. If \dost(x,s)<2−b−eα, put x into As (note that no-one has raised the \cost cost for x above \dost(x,s) yet), add α to γe. Say that Re acts.
Clearly Re only acts 2\sinit(e)=1/α times while it is not initialised.
\begin{claim} A⊨\cost. \end{claim}
When Re acts at s we have \cost(x,s)≤2−b−eα by initialisation.
\begin{claim} TA⊨\cost. \end{claim}
Otherwise TA⊨\cost via some enumeration \seq {\Phi_e} such that \cost \seq {\Phi_e} \lt 1. Since \dost satisfies the limit condition, γe reaches the value 1. This is at least what \seq {\Phi_e} pays for the enumerations of x−1 into TA. For when Re acts at s via x then x−1∈Φe(u) for some u>x since s is e-expansionary. By the next e-expansionary stage we have x−1∈Φe(u′) for some u′>u. So Φe paid the cost \cost(x−1,x+1)≥α that was set by Re at stage x.
\end{proof}
\part{Computability theory}
4. Merkle, Nies and Stephan: A dual of the Gamma question
Merkle, Nies and Stephan worked at NUS in February. They considered a dual of the Γ operator on Turing degrees.
For Z⊆N the lower density is defined to be
ρ(Z)=nliminfn∣Z∩[0,n)∣.
Recall that
γ(A)=Xcomputablesupρ(A↔X)
Γ(A)=inf{γ(Y):Y≤TA}
which only depends on the Turing degree of A. The Γ operator was introduced by Andrews, Cai, Diamondstone, Jockusch and Lempp 1.
\begin{definition}
δ(A)=Xcomputableinfρ(A↔X)
Δ(A)=sup{δ(Y):Y≤TA}.
\end{definition}
Intuitively, \bi \item Γ(A) measures how well computable sets can approximate the sets that A computes, counting the asymptotically worst case (the infimum over all Y≤TA). In contrast, \item Δ(A) measures how well the sets that A computes can approximate the computable sets, counting the asymptotically best case (the supremum over all Y≤TA).
\ei
Clearly the maximum value of Δ(A) is 1/2. The operator Δ(A) is related to the analog of a cardinal characteristic introduced by Brendle and Nies in the 2015 Logic Blog~12. They define \+B(∼p) to be the class of oracles A that compute a set Y such that for each computable set X, we have ρ(X↔Y)>p. For each p with 0≤p<1/2,
\bc Δ(A)>p⇒A∈\+B(∼p)⇒Δ(A)≥p. \ec
We state three minor results.
\begin{prop} Let A be 2-generic. Then Δ(A)=0. \end{prop}
A proof is given at the end of Section~Section 2.
\begin{prop} Let A compute a Schnorr random Y. Then Δ(A)=1/2. \end{prop}
This is clear because ρ(Y↔R)=1/2 for each computable R.
\begin{prop} Let p∈(0,1/2) be computable. Let A be Schnorr random for the Bernoulli measure w.r.t.\ p. Then δ(B)=p for each B≡1A. \end{prop}
The ``Δ-question" is (or rather, was, and has been quite short-lived):
\begin{question}[solved] Can Δ(A) be properly between 0 and 1/2? \end{question}
Using a dual form of Monin's technique's below, this has been answered in the negative by Nies; see Section~Section 2.
5. Monin - A resolution of the Gamma question
We show that there is no sequence X with a Gamma value strictly between 0 and 1/2.
\begin{definition}
For a given n∈ω and two strings σ1,σ2∈2n, the notation d(σ1,σ2) denotes the normalised hamming distance between σ1 and σ2, that is, the number of bits on which σ1 and σ2 differ divided by n.
\end{definition}
\begin{definition}
Let F:ω→ω be a function. Given a function f such that f(n)<2F(n), for each n, by [f(n)] we denote the string of length F(n) encoded by f(n).
\end{definition}
The following weakens the notion of infinitely often equal (i.o.e.) for a computable bound, which was first studied in 29.
\begin{definition}
Let F:ω→ω be a function and α∈[0,1]. A function f is 2F(n)-infinitely often α-equal if for every computable function g:ω→ω which is bounded by 2F(n), we have:
nliminfd([f(n)],[g(n)])≤1−α
Informally, we want f to equal infinitely often on a fraction of at least α bits, to every computable function bounded by 2F(n). Typically we will have α>1/2.
\end{definition}
\begin{proposition}
Let 1/2<α<1. Suppose that for no k, X computes a function which is 2⌊2n/k⌋-i.o.α-e. Then Γ(X)≥1−α.
\end{proposition}
\begin{proof}
Consider any sequence Y computed by X. Fix some c∈ω and let k be the smallest integer such that 21/k−1<1/(2c). We then split Y in blocks of bits of length ⌊2n/k⌋. We now argue that for n large enough, the number of bits in the n+1-th block is smaller than 1/c times the sum of the number of bits in the previous blocks. By the sum of geometric series we have:
Thus the length of the n+1 block of bit is smaller than 1/c of the sum of the length of the previous blocks.
Define the function f<2⌊2n/k⌋ by setting f(n) to the value coded by the bits of the n-th block. Suppose that f is not 2⌊2n/k⌋ i.o.α-e. In particular there must be some computable function h≤2⌊2n/k⌋ such that for almost every n, [h(n)] agrees with [f(n)] on a fraction of strictly less than α bits. Let h′ be defined as the complement of h bitwise. Then for almost every n, [h′(n)] agrees with [f(n)] on a fraction of bits strictly bigger than 1−α.
Now consider the bit number m of the sequence defined by f, starting at the begining of a block. Let m+n be the last position of that block. By hypothesis, among the m first bits (for m large enough), there are at least m(1−α)−O(1) bits which are guessed correctly by h′. In particular, for any 1≤i≤n, there are also at least m(1−α)−O(1) bits which are guessed correctly among the m+i first bits. Also for any 1≤i≤n, the number of total bits is at most m+n, which is at most m+m/c. Thus for each i the fraction of bits which are guessed correctly before m+i is at least:
m+m/cm(1−α)−O(1)
As m goes to infinity, this value converges to:
1+1/c1−α
Thus γ(Y)≥1+1/c1−α. We can carry out this argument for c larger and larger, making lower bounds on γ(Y) closer and closer to 1−α. Thus if for any k, we can split any Y into blocks of bits as above such that the resulting function is not 2⌊2n/k⌋-i.o.α-e., then γ(Y)≥1−α. By hypothesis we can do this for every Y computable by X. Hence Γ(X)≥1−α.
\end{proof}
By contrapositive, if Γ(X)<(1−α), for 1/2<α<1, then for some k∈ω, X computes a function which is 2⌊2n/k⌋-i.o.α-e. \\
We now need to borrow some technics from the field of error correcting codes. The idea is the folloing: We want to transmit some message of length m. But some random bit flip can occur during the transmission. We want to make sure that if the percentage of error is small enough, we can still recover the original message. The idea is to use an injection Φ from 2m into 2n for some n>>m, in such a way that the elements in the range of Φ, are pairwise far away from each other, in the sense of the hamming distance. If d is the smallest distance between two elements in the range of Φ, then it is clear that we can recover up to d/2 error.
Also we would like n to be not much bigger than m (ideally a multiplicative constant). It is easy to find such a multiplicative constant allowing, to have a list of 2m elements of 2n, which are all at a distance of at least 1/2−ϵ from each other, for ϵ as small as we want. Thus it is possible to correct this way, up to a fraction 1/4 of error. It is not anymore possible if the fraction is bigger than 1/4. However, if the fraction is smaller than 1/2, it is possible to identify a small list of messages, among which must figure our original message. It is even possible to make the size of the list constant. Formally we use the following theorem, for which we provide a proof for completness:
\begin{theorem}[The list decoding capacity theorem]
Let 0<θ<1/2. There exists L∈ω and 0<R<1 as follows.
For any n, there exists a set C of 2⌊Rn⌋ many strings of length n such that for any string σ of length n, there are at most L strings τ in C such that d(σ,τ)<θ.
\end{theorem}
\begin{proof}
We prove that for parameters L and R well chosen, if we pick at random the strings in C, the theorem is true with positive probability.
Let β=2(1/2−θ)2log(e) and pick L such that β−L1>0. Then pick R such that R<β−L1.\\
Using Chernoff bounds, for any string τ of length n, the measure of the set {[σ]:∣σ∣=n and d(τ,σ)<θ} is bounded by e−2(1/2−θ)2n=2−βn. Thus, given a string σ the probability that picking a string τ at random gives d(σ,τ)<θ, is bounded by 2−βn.
Now let q=⌊Rn⌋ and let C be a collection of 2q strings picked at random. For any subset of L+1 of these strings, the probability that a given string σ has a hamming distance smaller than θ with each of them is bounded by 2−βn(L+1). Thus the probability that a given σ has a hamming distance smaller than θ with any possible subsets of size L+1 of C is bounded by (L+12q)2−βn(L+1). And the probability that this happens for any string σ is bounded by 2n(L+12q)2−βn(L+1). The following computation shows that this quantity is smaller than 1:
It follows that that for any n, if C is a collection of 2⌊Rn⌋ strings of length n that we pick at random, the probability that no string σ of length n has a hamming distance smaller than θ with more than L strings of C, is positive. In particular, for any n, there exists such a collection of strings.
\end{proof}
We can now prove that only 0, 1/2 and 1 can be realized by Γ values of sequences. First by 29, if X compute a function bounded by 2(2n) which equals infinitely often every computable function bounded by 2(2n), then Γ(X)=0: First, it is also easy to show that if f is 2(2n)-i.o.e., then for any c, f computes a function which is 2(2c×n)-i.o.e.
Second, it is easy to show that if f is 2(2c×n)-i.o.e. then γ(f)<1/(c+1).
\begin{theorem}
Let 1/2<α<1. If Γ(X)<1−α then X is 2(2n)-i.o.e. and hence Γ(X)=0.
\end{theorem}
\begin{proof}
Suppose Γ(X)<1−α. In particular from \cref{yoyo}, X computes a function f which is 2⌊2n/k⌋-i.o.α-e. for some k∈ω.
Using \cref{list_decod}, we pick L∈ω and 0<R<1 such that for any n, there exists a collection Cn of 2⌊Rn⌋ strings of length n, such that no string σ of length n has a Hamming distance less than θ=1−α with more than L strings of C. Note that such a collection of strings Cn is computable uniformly in n. Uniformly computable in n we fix a listing σ0n,σ1n,…σ2⌊Rn⌋−1n of the elements of Cn.
We define the following X-computable L-trace {Tn}n∈ω: For any n, Tn is the collection of integer i such that the hamming distance between [f(n)] and σi⌊2n/k⌋ is less than 1−α. Note that each Tn is X-computable uniformly in n and that ∣Tn∣≤L (possibly Tn is also empty). Note also that the values of Tn are bounded by 2⌊R2n/k⌋.
We claim that every computable function g<2⌊R2n/k⌋ is traced by Tn. Indeed, given such a computable function g, consider the computable function g′ defined by g′(n)=σi⌊2n/k⌋ if g(n)=i. We have that g′ is computable, and furthermore g′(n)≤2⌊2n/k⌋. As f is 2⌊2n/k⌋-i.o.α-e., there exist infinitely many m such that d([f(m)],[g′(m)])<1−α. Then, by definition of {Tn}n∈ω, we have g(m)∈Tm for each of these m.
Thus every computable function bounded by 2⌊R2n/k⌋ is captured infinitely often by {Tn}n∈ω.\\
Now, either the trace T2n must capture infinitely often every computable function bounded by 2⌊R22n/k⌋, or the trace T2n+1 must capture infinitely often every computable function bounded by 2⌊R2(2n+1)/k⌋, as otherwise, by combining the two computable witnesses that neither is the case, we would have a computable function bounded by 2⌊R2n/k⌋ and not traced by {Tn}n∈ω. In either case, {Tn}n∈ω can compute a trace which traces every function bounded by 2⌊R22n/k⌋ (Note that a trace capturing infinitely often every computable function bounded by F, also captures infinitely often every computable function bounded by G<F).
By iterating this argument, X can compute an L-trace {Tn}n∈ω which captures infinitely often every function bounded by 2L2n. We can also without loss of generality assume that each element of each Tn is bounded by 2L2n, and thus coded on exactly L2n bits. We now use the fact that ∣Tn∣≤L for every n, to compute using Tn a function h≤22n which is equal infinitely often to every computable function bounded by 22n.
First for every n, we add if necessary some elements in Tn such that ∣Tn∣=L. Then we view each element ei of Tn as an L-tuple ⟨ei1,…,eiL⟩. Formally eij is the j-th block of 2n consecutive bits. Consider L distinct X-computable functions h1,…,hL given by hi(n)=eii where ei=⟨ei1,…,eii,…,eiL⟩ is the i-th element of Tn. We claim that at least one hi is 2(2n)-i.o.e. Suppose otherwise, and consider the L computable functions p1,…,pL witnessing that. Then the computable function p(n)=⟨p1(n),…,pL(n)⟩ is never captured by Tn, as the i-th component of p(n) (seen as a L-tuple) is different from the i-th component of the i-th element of Tn (seen as a L-tuple). This contradicts our hypothesis. So at least one hi is 2(2n)-i.o.e.
Note that hi is computable from X. As in \cite[Thm.\ III.4]{Monin.Nies:15} from hi we can compute functions which are 2(an)-i.o.e. for any a∈ω; the binary sequence encoding each of these function have a γ value ≤1/a.
\end{proof}
Note that all the reductions are tt. Thus this also solves the Γ question in the tt degrees.
6. Brendle and Nies: Analog for cardinal characteristics of Monin's solution to the $\Gamma$ question
For background and definitions of the characteristics see last year's blog \cite[Section 7]{LogicBlog:15}. In analogy to Monin's post above, we will show that d(p)=d(=∗,2(2n)) and b(p)=b(=∗,2(2n)) for each p∈(0,1/2).
For convenience here are the main definitions:
Let R⊆X×Y be a relation between spaces X,Y (such as Baire space) satisfying $\forall x \; \exists y \;
(x R y)and\forall y \; \exists x \; \neg (x R y).LetS = \{ \langle y,x \rangle \in Y \times X \colon \neg xR y\}$.
\begin{definition} We write
\[ \frd(R) = \min\{|G|:G\subseteq Y \land \, \forall x \in X \,
\exists y \in G \, xR y\}.\]
\[ \frb(R) = \frd (S) = \min\{|F|:F\subseteq X \land \, \forall y\in Y
\exists x \in F \, \neg xR y\}.\]
\end{definition}
We will study d(R) and b(R) for two types of relations R.
\
\n 1. Let h:ω→ω (usually unbounded). Define for x∈ωω and
\n y∈Πn{0,…,h(n)−1},
\[ x \neq^*_h y \LR \fa^\infty n \, [ x(n) \neq y(n)]. \]
\
\n 2. Let 0≤p≤1/2. Define, for x,y∈ω2
\[ x \sim_p y \LR \underline \rho (x \lra y) >p, \]
where x↔y is the set of n such that x(n)=y(n), and ρ denotes the lower density: ρ(z)=liminfn∣z∩n∣/n.
\n It will be helpful to express Definition~ ? for these relations in words.
\
\n d(=h∗) is the least size of a set G of h-bounded functions so that for each function x there is a function y in G such that ∀∞n[x(n)=y(n)]. (Of course it suffices to require this for h-bounded x.)
\
\n b(=h∗) is the least size of a set F of functions such that for each h-bounded function y, there is a function x in F such that ∃∞nx(n)=y(n). (Of course we can require that each function in F is h-bounded.)
\
\n d(∼p) is the least size of a set G of bit sequences so that for each sequence x there is a sequence y in G so that ρ(x↔y)>p.
\
\n b(∼p) is the least size of a set F of bit sequences such that for each bit sequence y, there is a sequence x in F such that ρ(x↔y)≤p.
\begin{definition} Let h be a function of the form 2h^ with h^:ω→ω, and let Xh be the space of all h-bounded functions.
For such a function we view x(n) either as a number, or as a binary string of length h^(n) via the binary expansion with leading zeros allowed. We define Lh:Xh→ω2 by Lh(x)=∏nx(n), i.e. the concatenation of these strings. We let Kh:ω2→Xh be the inverse of Lh. \end{definition}
We begin with some preliminary facts of independent interest.
On occasion we denote a function λn.f(n) simply by f(n). The next lemma amplifies functions without changing the cardinal characteristics.
\begin{lemma} \bi \item[(i)] Let h be nondecreasing and g(n)=h(2n). We have d(=∗,h)=d(=∗,g) and b(=∗,h)=b(=∗,g).
\item [(ii)] For each a,b>1 we have d(=∗,2(an))=d(=∗,2(bn)) and
\n b(=∗,2(an))=b(=∗,2(bn)). \ei \end{lemma}
\begin{proof} (i) Trivially, h≤g implies that d(=∗,h)≥d(=∗,g) and b(=∗,h)≤b(=∗,g). So it suffices to show two inequalities.
\vsps
\n \fbox{d(=∗,h)≤d(=∗,g):} Let G be a witness set for d(=∗,g). Note that G is also a witness set for d(=∗,h(2n+1)). Let G^={p0⊕p1:p0,p1∈G}, where (p0⊕p1)(2m+i)=pi(m) for i=0,1. Each function in G^ is bounded by h. Since G is infinite, ∣G^∣=∣G∣. Clearly G^ is a witness set for d(=∗,h).
\vsps
\n \fbox{b(=∗,h)≥b(=∗,g):} Let F be a witness set for b(=∗,h). Let F^ consist of the functions of the form n→p(2n), or of the form n→p(2n+1), where p∈F. Then ∣F^∣=∣F∣, and each function in F^ is g bounded.
Clearly, F^ is a witness set for b(=∗,g): if q is g-bounded, then q^ is h bounded where q^(2n+i)=q(n) for i=0,1. Let p∈F be such that ∃∞kp(k)=q^(k). Let i≤1 be such that infinitely many such k have parity i. Then the function n→p(2n+i) which is in F^ is as required.
(ii) is immediate from (i) by iteration using that a2i>b and b2i>a for sufficiently large i.
\end{proof}
\begin{lemma} Let a∈ω−{0}. We have d(=∗,2(an))≤d(1/a) and
\n b(=∗,2(an))≥b(1/a).\end{lemma}
\begin{proof} Let Im for m≥2 be the m−1-th consecutive interval of length am in ω−{0}, i.e.
\[ I_m = \big [\frac{a^m-1}{a-1} , \frac{a^{m+1} -1 } {a-1}\big). \]
First let G be a witness set for d(1/a). Let h(n)=2(an). We show that G^={Kh(y):y∈G} is a witness set for d(=∗,2(an)). Otherwise there is a sequence z∈ω2 such that for each x∈ωω there are infinitely many m with x(m)=Kh(z)(m). Let y′ be the complement ω−z of z, that is 0s and 1s are interchanged. Then for infinitely many m, Lh(x)(i)=y′(i) for each i∈Im. If we let n=1+maxIm, the proportion of i<n such that Lh(x)(i)=y′(i) is therefore at most (am−1)/(am+1−1), which converges to 1/a as m→∞. This contradicts the choice of G.
Now let F be a witness set for b(=∗,h). Let F^={ω−Lh(x):x∈F}. For each y∈2N there is x∈F such that ∃∞nKh(y)(n)=x(n). This implies ρ(y↔x′)≤1/a where x′=ω−Lh(x)∈F^. Hence F^ is a witness set for b(1/a).
\end{proof}
\begin{thm} Fix any p∈(0,1/2). We have d(p)=d(=∗,2(2n)) and
\n b(p)=b(=∗,2(2n)). \end{thm}
\begin{proof} By the two foregoing lemmas we have d(p)≥d(=∗,2(2n)) and b(p)≤b(=∗,2(2n)). It remains to show the converse inequalities:
\n d(p)≤d(=∗,2(2n)) and b(p)≥b(=∗,2(2n)).
\begin{definition} For strings x,y of length r, the normalised Hamming distance is defined as the proportion of bits on which x,y disagree, that is,
\[ d(x,y) = \frac 1 r |\{ i \colon x(n) (i) \neq y(n)(i) \}| \] \end{definition}
\begin{definition} Let h be a function of the form 2h^ with h^:ω→ω, and let X=Y=Xh be the space of h-bounded functions. Let q∈(0,1/2).
We define a relation on X×Y by
\[x \neq^*_{\hat h,q} y \LR \fa^\infty n \, [ d(x(n), y(n)) \ge q] \]
namely for a.e. n the strings x(n) and y(n) disagree on a proportion of at least q of the bits. We will usually write ⟨=∗,h^,q⟩ for this relation. \end{definition}
\begin{claim} For each c∈ω there is k∈ω such that \bc d(q−2/c)≤d⟨=∗,⌊2n/k⌋,q⟩, and \ec
\bc b(q−2/c)≥b⟨=∗,⌊2n/k⌋,q⟩. \ec \end{claim}
\n To see this, let k be large enough so that 21/k−1<2c1. Let h^(n)=⌊2n/k⌋ and h=2h^. Write H(n)=∑r≤nh^(r). Given an infinite bit sequence, we refer to the bits with position in an interval [H(n),H(n+1)) as Blockn (the first block is Block 0). By Monin's 2016 logic blog entry, for sufficiently large n,
\[ \hat h(n+1) \le \frac 1 c H(n). \]
For the inequality involving d, let G be a witness set for d⟨=∗,h^,q⟩. Thus, for each function x<h there is a function y∈G such that for almost all n, Lh(x),Lh(y) disagree on a proportion of q bits of Block n. Let z be the complement of Lh(y). Given m, let n be such that H(n)≤m<H(n+1). Since m−H(n)≤c1H(n), for large enough m, Lh(x) and z agree up to m on a proportion of at least q−1.5/c bits. So the set of complements of the Lh(y), y∈G, forms a witness set for d(q−2/c) as required.
For the inequality involving b, let F be a witness set for b(q−2/c). Thus, for each y∈2N there is x∈F such that ρ(y↔x)≤q−2/c. Let F^={Kh(1−x):x∈F}. We show that F^ is a witness set for b⟨=∗,⌊2n/k⌋,q⟩.
Give a function y<h, let y′=Lh(y). There is x∈F such that ρ(y′↔x)≤q−2/c, and hence ρ(y′↔x′)≥1−q+2/c where x′=1−x is the complement and ρ denotes the upper density. Then there are infinitely many m such that the strings y′↾m and x′↾m agree on a proportion of >q+1/c bits.
Suppose that H(n)≤m<H(n+1) then the contribution of disagreement of Block n is at most 1/c. So
there are infinitely many k so that in Block k, y′ and x′ agree on a proportion of more than 1−q bits, and hence disagree on a proportion of fewer than q bits.
This shows the claim.
As in Monin's entry we use the list decoding capacity theorem from the theory of error-correcting codes. Given q as above and L∈ω, for each r there is a ``fairly large" set C of strings of length r (the allowed code words) such that for each string, at most L strings in C have normalised Hamming distance less than q from σ. (Hence there is only a small set of strings that could be the error-corrected version of σ.) Given string σ of length r, let Bq(σ) denote an open ball around σ in the normalised Hamming distance, namely, B_q(\sss) = \{ \tau \in {}^r 2 \colon \, \sigma, \tau \text{ disagree on fewer thanqrbits}\}
\begin{lemma}[List decoding] Let q∈(0,1/2). There are ϵ>0 and L∈ω such that for each r, there is a set C of 2⌊ϵr⌋ strings of length r as follows: \bc ∀σ∈r2[∣Bq(σ)∩C∣≤L]. \ec
\end{lemma}
For L∈ω, an L-slalom is a function s:ω→ω[≤L], i.e.\ a function that maps natural numbers to sets of natural numbers with a size of at most L.
\begin{definition} Fix a function u:ω→ω and L∈ω. Let X be the space of L-slaloms s such that maxs(n)<u(n) for each n, and let Y be the set of functions such that y(n)<u(n) for each n. Define a relation on X×Y by
\[s \not \ni^*_{u,L} y \LR \fa^\infty n [s(n) \not \ni y(n)]. \]
We will write ⟨∋∗,u,L⟩ for this relation.
\end{definition}
\begin{claim} Given q<1/2, let L,ϵ be as in Lemma~ ?. Fix a nondecreasing function h^, and let u(n)=2⌊ϵh^(n)⌋. We have
\[ \frd \la \neq^, \hat h , q\ra \le \frd \la \not \ni^, u,L \ra \text{ and } \frb \la \neq^, \hat h , q\ra \ge \frb \la \not \ni^, u,L \ra. \]
\end{claim}
For the inequality involving d, let G be a set of functions bounded by u such that ∣G∣<d⟨=∗,h^,q⟩. We show that G is not a witness set for the right hand side d⟨∋∗,u,L⟩.
For each r of the form h^(n) choose a set C=Cr as in Lemma~ ?. Since ∣Cr∣=2⌊ϵr⌋ we may choose a sequence \seq {\sss^r_i}_{i\lt \tp{\lfloor \epsilon r \rfloor}} listing Cr without repetitions. For a function y<u let y be the function given by y(n)=σy(n)h^(n). Thus y(n) is a binary string of length h^(n). Let G={y:y∈G}. Then ∣G∣=∣G∣<d⟨=∗,h^,q⟩. So there is a function x with x(n)∈h^(n)2 for each n such that for each y∈G^ we have ∃∞n[d(x(n),y(n))<q]. Let s be the slalom given by
\[ s(n) = \{ i \colon \, d (x(n), \sss^{\hat h(n)}_i )< q \}.\]
Note that by the choice of the Cr according to Lemma~ ?, s is an L-slalom. By the definitions, for each y∈G we have ∃∞n[s(n)∋y(n)]. So G is not a witness set for d⟨∋∗,u,L⟩.
For the inequality involving b, suppose F is a witness set for b⟨=∗,h^,q⟩. That is, for each h=2h^-bounded function y, there is x∈F such that
\bc ∃∞n[d(x(n),y(n)<q] \ec (as usual we view x(n),y(n) as binary strings of length h^(n)).
For x∈F let sx be the L-slalom such that
\bc sx(n)={i<u(n):d(σih^(n),x(n))<q}. \ec
Let F^={sx:x∈F}. Given an u-bounded function y, let y′(n)=σy(n)h^(n). There is x∈F such that d(x(n),y′(n)<q for infinitely many n. This means that y(n)∈sx(n). Hence F^ is a witness set for
b⟨∋∗,u,L⟩. This shows the claim.
We next need an amplification tool in the context of slaloms. The proof is almost verbatim the one in Lemma~ ?(i), so we omit it.
\begin{claim} Let L∈ω, let the function u be nondecreasing and let w(n)=u(2n). We have d(⟨∋∗,u,L⟩=d⟨∋∗,w,L⟩ and b(⟨∋∗,u,L⟩=b⟨∋∗,w,L⟩.
\end{claim}
Iterating the claim, starting with the function h^(n)=⌊2n/k⌋ with k as in Claim~ ?, we obtain that d⟨∋∗,2h^,L⟩=d⟨∋∗,2(L2n),L⟩, and similarly for b.
It remains to verify the following.
\begin{claim} d⟨∋∗,2(L2n),L⟩≤d(=∗,2(2n)) and
\n b⟨∋∗,2(L2n),L⟩≥b(=∗,2(2n)). \end{claim}
Given n, we write a number k<2(L2n) in binary with leading zeros if necessary, and so can view k as a binary string of length L2n. We view such a string as consisting of L consecutive blocks of length 2n.
For the inequality involving d,
let G be a witness set for d(=∗,2(2n)). For functions y1,…,yL such that yi(n)<2(2n) for each n, let (y1,…,yL) denote the function y with y(n)<2(L2n) for each n such that the i-th block of y(n) equals yi(n) for each i with 1≤i≤L. Let
\bc G^={(y1,…,yn):y1,…,yL∈G}. \ec
Since G is infinite we have ∣G^∣=∣G∣. We check that G^ is a witness set for the left hand side d⟨∋∗,2(L2n)⟩. Given an L-slalom s bounded by 2(L2n) we may assume that s(n) has exactly L members, and they are binary strings of length L2n. For i≤L let xi(n) be the i-th block of the i-th string in s(n), so that ∣xi(n)∣=2n. Viewing the xi as functions bounded by 2(2n), we can choose y1,…,yL∈G such that ∀∞nxi(n)=yi(n). Let y=(y1,…,yn)∈G^. Then ∀∞n[s(n)∋y(n)], as required.
For the inequality involving b let F be a witness set for b⟨∋∗,2(L2n). That is, F is a set of L-slaloms s such that for each function y with y(n)<2(L2n), there is s∈F such that s(n)∋y(n) for infinitely many n.
Let F^ be the set of functions si, for s∈F and i<L, such that si(n) is the i-th block of the i-th element of s(n) (as before we may assume that each string in s(n) has length L2n). Now let y be a given function bounded by 2(2n). Let y′ be the function bounded by 2(L2n) such that for each n, each block of y′(n) equals y(n). There is s∈F such that s(n)∋y′(n) for infinitely many n. There is i<L such that , y′(n) is the i-th string in s(n) for infinitely many of these n, and hence y(n)=si(n). Thus F^ is a witness set for b(=∗,2(2n)).
This proves the claim.
We can now summarise the argument that d(p)≤d(=∗,2(2n)). Pick c large enough such that q=p+2/c<1/2.
By Claim~ ? there is k such that \bc d(p)≤d⟨=∗,⌊2n/k⌋,q⟩. \ec
By Claim~ ? there are L, ϵ such that where h^(n)=⌊2n/k⌋, we have \bc d⟨=∗,h^,q⟩≤d⟨∋∗,u,L⟩, \ec
where u(n)=2⌊ϵh^(n)⌋.
Applying Claim~ ? sufficiently many times we have \bc d⟨∋∗,u,L⟩≤d⟨∋∗,2(L2n),L⟩. \ec
\n Finally, d⟨∋∗,2(L2n),L⟩≤d(=∗,2(2n)) by Claim~ ?. The argument for b(p)≥b(=∗,2(2n)) is the exact dual.
\end{proof}
7. Nies: answering the $\Delta$ question
We use the notation in 5. Let R⊆X×Y be a relation between spaces X,Y, and let S={⟨y,x⟩∈Y×X:¬xRy}.
Suppose we have specified what it means for objects x in X, y in Y to be computable in a Turing oracle A. We denote this by for example x≤TA. In particular, for A=∅ we have a notion of computable objects.
Let the variable x range over X, and let y range over Y. We define the highness properties
\[ \+ B(R) = \{ A: \,\exists y \leT A \, \fa x \ \text{computable} \ [xRy] \} \]
\[ \+ D(R) = \+ B(S) = \{ A: \,\exists x \leT A \, \fa y \ \text{computable} \ [\neg xRy] \} \]
\n 1. Let h:ω→ω−{0,1}. Define for x∈ωω and
\n y∈∏n{0,…,h(n)−1}⊆ωω,
\[ x \neq^*_h y \LR \fa^\infty n \, [ x(n) \neq y(n)]. \]
\n 2. Let 0≤p≤1/2. Define, for x,y∈ω2
\[ x \sim_p y \LR \underline \rho (x \lra y) >p, \]
where x↔y is the set of n such that x(n)=y(n), and ρ denotes the lower density: ρ(z)=liminfn∣z∩n∣/n.
It may be helpful to separately state two special cases.
\begin{definition} For a computable function h, we let \+B(=h∗) denote the class of oracles A that compute a function y<h such that for each computable function x, we have ∀∞nx(n)=y(n).
For p<1/2, we let \+B(∼p), or \+B(p) for short, denote the class of oracles A that compute a set y such that for each computable set x, we have ρ(x↔y)>p. \end{definition}
Recall Definition~ ? and that for each p with 0≤p<1/2,
\bc Δ(A)>p⇒A∈\+B(∼p)⇒Δ(A)≥p. \ec
We show that \+B(∼p)=\+B(=∗,2(2n)) for each p∈(0,1/2). In particular, Δ(A)>0⇒Δ(A)=1/2 so there are only two possible Δ values.
We begin with some preliminary facts of independent interest.
On occasion we denote a function λn.f(n) simply by f(n).
\begin{lemma} \bi \item[(i)] Let h be nondecreasing and g(n)=h(2n). We have \+B(=∗,h)=\+B(=∗,g).
\item [(ii)] For each a,b>1 we have \+B(=∗,2(an))=\+B(=∗,2(bn)). \ei \end{lemma}
\begin{proof} (i) Trivially, h≤g implies that \+B(=∗,h)⊆\+B(=∗,g). So it suffices to show the converse inclusion \+B(=∗,h)⊇\+B(=∗,g).
Let y≤TA, y<g be a function witnessing that A∈B(=∗,g). Let y^(2n+i)=y(n) for i≤1, so that y^<h. Given any computable function x, for almost every n we have x(2n)=y(n) and x(2n+1)=y(n). Therefore ∀∞n[x(n)=y^(n)]. Hence y^ is a witness for A∈B(=∗,h).
(ii) is immediate from (i) by iteration using that a2i>b and b2i>a for sufficiently large i.
\end{proof}
Recall Def.\ ? of the Lh and Kh operators.
\begin{lemma} Let a∈ω−{0}. We have \+B(=∗,2(an))⊇\+B(1/a). \end{lemma}
\begin{proof} Let Im for m≥2 be the m−1-th consecutive interval of length am in ω−{0}, i.e.
\[ I_m = \big [\frac{a^m-1}{a-1} , \frac{a^{m+1} -1 } {a-1}\big). \]
Let h(m)=2am. Let y≤TA witness that A∈\+B(1/a), and let y^=Kh(y). Given a computable function x<h, let x′=1−Lh(x). Since ρ(x′↔y)>1/a, for large enough n, there is k∈In such that x′(i)=y(i). Hence we cannot have x(n)=y^(n). Thus y^ witnesses that A∈\+B(=∗,2(an)).
\end{proof}
A similar argument shows that \+B(=∗,2h^(m))⊇\+B(0) for any computable function h^ such that ∀a∀∞mh^(m)≥am. Now the m-th interval has length h^(m).
\begin{thm} Fix any p∈(0,1/2). We have \+B(p)=\+B(=∗,2(2n)). \end{thm}
\begin{proof} The two foregoing lemmas imply \+B(p)⊆\+B(=∗,2(2n)). It remains to show the converse inclusion \+B(p)⊇\+B(=∗,2(2n)).
\begin{definition} For strings x,y of length r, the normalised Hamming distance is defined as the proportion of bits on which x,y disagree, that is,
\[ d(x,y) = \frac 1 r |\{ i \colon x(n) (i) \neq y(n)(i) \}| \] \end{definition}
\begin{definition} Let h be a function of the form 2h^ with h^:ω→ω, and let X=Y=Xh be the space of h-bounded functions. Let q∈(0,1/2).
We define a relation on X×Y by
\[x \neq^*_{\hat h,q} y \LR \fa^\infty n \, [ d(x(n), y(n)) \ge q] \]
namely for a.e. n the strings x(n) and y(n) disagree on a proportion of at least q of the bits. We will usually write ⟨=∗,h^,q⟩ for this relation. \end{definition}
The first step makes the crucial transition from the density setting to the combinatorial setting.
\begin{claim} Let q∈(0,1/2). For each c∈ω such that 2/c<q, there is k∈ω such that \bc \+B(q−2/c)⊇\+B⟨=∗,⌊2n/k⌋,q⟩. \ec \end{claim}
\n To see this, let k be large enough so that 21/k−1<2c1. Let h^(n)=⌊2n/k⌋ and h=2h^. Write H(n)=∑r≤nh^(r). Given an infinite bit sequence, we refer to the bits with position in an interval [H(n),H(n+1)) as Blockn (the first block is Block 0). By Monin's 2016 logic blog entry, for sufficiently large n,
\[ \hat h(n+1) \le \frac 1 c H(n). \]
Let y≤TA be a witness for A∈\+B⟨=∗,⌊2n/k⌋,q⟩. Thus, y<h and ∀∞n[d(Lh(x)(n),Lh(y)(n)≥q]. Let y′=1−Lh(y). Then \bc ∀∞n[d(x′(n),y′(n))<q] \ec for each computable x′∈2N. Suppose that H(n)≤m<H(n+1). Then the contribution of Block n to the proportion of disagreement between x′,y′ is at most 1/c.
So ρ(y′↔x′)>q−2/c. Hence y′≤TA is a witness for A∈\+B(q−2/c).
This shows the claim.
For L∈ω, an L-slalom is a function s:ω→ω[≤L], i.e.\ a function that maps natural numbers to sets of natural numbers with a size of at most L.
\begin{definition} Fix a function u:ω→ω and L∈ω. Let X be the space of L-slaloms (or traces) s such that maxs(n)<u(n) for each n. Thus s maps natural numbers to sets of natural numbers of size at most L, represented by strong indices. Let Y be the set of functions such that y(n)<u(n) for each n. Define a relation on X×Y by
\[s \not \ni^*_{u,L} y \LR \fa^\infty n [s(n) \not \ni y(n)]. \]
We will write ⟨∋∗,u,L⟩ for this relation.
\end{definition}
\begin{claim} Given q<1/2, let L,ϵ be as in Lemma~ ?. Fix a nondecreasing computable function h^, and let u(n)=2⌊ϵh^(n)⌋. We have \bc \+B⟨=∗,h^,q⟩⊇\+B⟨∋∗,u,L⟩. \ec
\end{claim}
For each r of the form h^(n) compute a set C=Cr as in Lemma~ ?. Since ∣Cr∣=2⌊ϵr⌋ there is a uniformly computable sequence \seq {\sss^r_i}_{i\lt \tp{\lfloor \epsilon r \rfloor}} listing Cr in increasing lexicographical order.
Suppose that y≤TA is a witness for
A∈\+B⟨∋∗,u,L⟩. Let y<h be the function given by y(n)=σy(n)h^(n).
We show that y is a witness for
\n A∈\+B⟨=∗,h^,q⟩.
For a computable function x<h, let sx be the computable L-trace such that
\bc sx(n)={i<u(n):d(σih^(n),x(n))<q}. \ec
Since y is a witness for A∈\+B⟨∋∗,u,L⟩, for almost every n we have y(n)∈sx(n). Hence d(y(n),x(n)≥q, as required.
We next need an amplification tool in the context of traces. The proof is almost verbatim the one in Lemma~ ?(i), so we omit it.
\begin{claim} Let L∈ω, let the computable function u be nondecreasing and let w(n)=u(2n). We have \+B(⟨∋∗,u,L⟩=\+B⟨∋∗,w,L⟩.
\end{claim}
Iterating the claim, starting with the function h^(n)=⌊2n/k⌋ with k as in Claim~ ?, we obtain that \+B⟨∋∗,2h^,L⟩=\+B⟨∋∗,2(L2n),L⟩.
It remains to verify the following, which would work for any computable function h^(n) in place of the 2n in the exponents.
\begin{claim} \+B⟨∋∗,2(L2n),L⟩⊇\+B(=∗,2(2n)). \end{claim}
Given n, we write a number k<2(L2n) in binary with leading zeros if necessary, and so can view k as a binary string of length L2n. We view such a string as consisting of L consecutive blocks of length 2n.
Let y be a witness function for \+B(=∗,2(2n)). That is, y<2(2n) and ∀∞nx(n)=y(n) for each computable function x. Let y′ be the function bounded by 2(L2n) such that for each n, each block of y′(n) equals y(n).
Given a computable L-trace s with maxs(n)<2(L2n), for i<L let xi be the computable function such that xi(n) is the i-th block of the i-th element of s(n) (as before we may assume that each string in s(n) has length L2n). For sufficiently large n, we have ∀i<Ly(n)=xi(n). Hence ∀∞ns(n)∋y′(n) and y′ is a witness for A∈\+B⟨∋∗,2(L2n).
We can now summarise the argument that \+B(p)⊇\+B(=∗,2(2n)). Pick c large enough such that q=p+2/c<1/2.
By Claim~ ? there is k such that \bc \+B(p)⊇\+B⟨=∗,⌊2n/k⌋,q⟩. \ec
By Claim~ ? there are L, ϵ such that where h^(n)=⌊2n/k⌋ and u(n)=2⌊ϵh^(n)⌋, we have \bc \+B⟨=∗,h^,q⟩⊇\+B⟨∋∗,u,L⟩. \ec
Applying Claim~ ? sufficiently many times we have \bc \+B⟨∋∗,u,L⟩⊇\+B⟨∋∗,2(L2n),L⟩. \ec
\n Finally, \+B⟨∋∗,2(L2n),L⟩⊇\+B(=∗,2(2n)) by Claim~ ?. \end{proof}
We note that by the proofs, both inclusions in Theorem~ ? are uniform in a strong sense: from a witness y≤TA for one property one can compute a witness y′ for the other property.
As a corollary to Theorem~ ? we obtain a proof of Proposition~ ?. If A is 2-generic then A is neither high nor d.n.c., so A is not in \+B(=∗)=high or d.n.c. the class where no bound is imposed on the witness function A computes. So A is not in B(=∗,2(2n)), hence Δ(A)=0.
\part{Reverse mathematics}
8. Belanger, Nies and Shafer: the strength of randomness existence axioms
David Belanger, Andr\'e Nies and Paul Shafer others discussed the strength of randomness existence axioms at NUS and University of Ghent in February/March.
In \cite[Section.\ 9]{LogicBlog:13}, for a randomness notion \+C, we defined \+C0 to be the system RCA+∀X∃YY∈\+CX. For instance, \MLR_0 is equivalent to weak weak K\"onigs Lemma over RCA.
The system CR0 (computable randomness) appears to be equivalent to the seemingly weaker SR0 (Schnorr randomness) (\cite[Prop.\ 9.2]{LogicBlog:13}; the strength of induction axioms that are needed to show this remains to be checked carefully).
2-randomness versus weak 2-randomness
On the other hand 2R0 (the system for 2-randomness) is strictly stronger than
W2R0 (the system for weak 2 randomness). To see this, take a weakly 2-random Z that does not compute a 2-random. For instance, any 2-random has hyperimmune degree. Any computably dominated ML-random Z is weakly 2-random and hence does not compute a 2-random. For each n let Zn be the n-th column of Z, that is, Zn={k:⟨k,n⟩∈Z}. Let \+M=(N,\+S) where \+S consists of all the sets Turing below the join of finitely many columns of Z. Note that Zn is weakly 2-random in any finite sum of columns not containing Zn. So \+M is a model of W2R0.
We can also separate the two randomness existence axioms via an interesting mathematical consequence: Csima and Mileti~8 have shown that 2R0 implies the Rainsey Rambo's theorem.
\begin{prop} W2R0 does not imply the Rainbow Ramsey's theorem. \end{prop}
\begin{proof} Joseph Miller has shown that the Rainbow Ramsey's theorem is equivalent over RCA0 plus some induction to the existence of a d.n.c.\ function relative to ∅′. (Detail needed here on the construction for the forward direction: recursive in a homogeneous set we obtain the function.) By \cite[Exercise 4.3.18]{Nies:book} there is a weakly 2-random set Z that does not compute a 2-fixed point free function, and hence it computes no d.n.c.\ function relative to ∅′. Construct the model \+M⊨W2R0 from Z as above. Then Rainbow Ramsey's theorem fails in \+M.
\end{proof}
Weak Demuth randomness versus \mathtt{WKL}
\begin{definition}
A Δ20 function f is ω-c.e.\ if there is a computable function h such that h(n) bounds the number of changes in a computable approximation to f(n).
A Demuth test is an effective sequence \seq{\+ U_n} of effectively open (Σ10) subsets of Cantor space such that:
1. For all n, the measure λ(\+Un) of \+Un is bounded by 2−n; and
2. there is an ω-c.e.\ function mapping n to a Σ10 index for \+Un.
A set (an element of Cantor space) X is captured by a Demuth test \seq{\+ U_n} if X∈\+Un for infinitely many n. A set is Demuth random if it is not captured by any Demuth test.
A set Zweakly passes a test \seq{\+ U_n} if Z∈⋂n\+Un. A set Z is weakly Demuth random if it weakly passes every Demuth test.
\end{definition}
Figueira et al.\ 13 introduced balanced randomness, a notion in between weak Demuth randomness and ML-randomness where the m-th test component \+Um of a test can be ``replaced" at most O(2m) times. This notion is still stronger than Oberwolfach randomness. More generally, for an order function h we say that Z is h- weak Demuth random if it weakly passes each Demuth test where the component \+Um can be replaced at most h(m) times.
It was observed in 3 that the methods of 13 show the following.
\begin{prop} Let Z=Z0⊕Z1 be ML-random. Then Z0 or Z1 is balanced random, and in fact O(r(n)2n)-weak Demuth random for some order function r. \end{prop}
\begin{proof} We use the terminology of 13. If Z0 is ω-c.e.\ tracing then any weak Demuth test (which is given by an ω-c.e.\ function) can be converted into a ML-test relative to Z0. So by van Lambalgen theorem, Z1 is weak Demuth random.
If Z0 is not ω-c.e.\ tracing then by \cite[Thm.\ 23]{Figueira.Hirschfeldt.ea:15} Z0 is O(r(n)2n)-weak Demuth random for some order function r, and in particular, balanced random.
\end{proof}
So weak weak K\"onigs lemma plus sufficient induction implies the axiom for balanced randomness.
\begin{definition} For a computable function h, we say that a set Z is h-c.e.\ if there is a computable approximation such that Z↾n changes at most h(n) times. For instance, each left-c.e.\ set is 2n-c.e. \end{definition}
Such a set is clearly not h-weak Demuth random. So the following ω-model \+M satisfies WKL but not the axiom for weak h-Demuth randomness, for any function h that dominates each function λn.kn , such as h(n)=2n⋅p(n) for some order function p.
\begin{prop} There is an ω-model \+M of WKL such that each set of \+M is superlow and kn-c.e.\ for some k∈N. \end{prop}
\begin{proof} Let \+S(X) be the Π10 class relative to X of sets that are PA-complete in X. Over RCA, the axiom WKL is equivalent to ∀X\+S(X)=∅.
Let \+Q be the Π10 class consisting of the sets Y such that Yi+1∈\+S(⨁k≤iYk) for each i; here Yi={n:⟨i,n⟩∈Y} is the i-th column of Y.
If Y∈\+Q then the Turing ideal generated by the columns of Y determines an ω-model \+M of WKL.
Let X→WX be the c.e.\ operator such that
\bc 2e(2n+1)∈WX⇔ΦeX(n)=1}. \ec
By the superlow basis theorem as stated in \cite[1.8.38]{Nies:book}, but with the operator W instead of the domain of the usual Turing jump J, there is Y∈\+Q such that WY is left-c.e.
Suppose that R=ΦeY. Since WY is left-c.e., R is 22e(2n+1)-c.e., and hence kn-c.e. where k=22e+2. Thus each set of \+M is kn-c.e.\ for some k∈N.
Clearly Y′≤mWY. So Y is superlow.
\end{proof}
9. Belanger, Nies and Shafer: the strength of randomness existence axioms
David Belanger, Andr\'e Nies and Paul Shafer others discussed the strength of randomness existence axioms at NUS and University of Ghent in February/March.
In \cite[Section.\ 9]{LogicBlog:13}, for a randomness notion \+C, we defined \+C0 to be the system RCA+∀X∃YY∈\+CX. For instance, \MLR_0 is equivalent to weak weak K\"onigs Lemma over RCA.
The system CR0 (computable randomness) appears to be equivalent to the seemingly weaker SR0 (Schnorr randomness) (\cite[Prop.\ 9.2]{LogicBlog:13}; the strength of induction axioms that are needed to show this remains to be checked carefully).
2-randomness versus weak 2-randomness
On the other hand 2R0 (the system for 2-randomness) is strictly stronger than
W2R0 (the system for weak 2 randomness). To see this, take a weakly 2-random Z that does not compute a 2-random. For instance, any 2-random has hyperimmune degree. Any computably dominated ML-random Z is weakly 2-random and hence does not compute a 2-random. For each n let Zn be the n-th column of Z, that is, Zn={k:⟨k,n⟩∈Z}. Let \+M=(N,\+S) where \+S consists of all the sets Turing below the join of finitely many columns of Z. Note that Zn is weakly 2-random in any finite sum of columns not containing Zn. So \+M is a model of W2R0.
We can also separate the two randomness existence axioms via an interesting mathematical consequence: Csima and Mileti~8 have shown that 2R0 implies the Rainsey Rambo's theorem.
\begin{prop} W2R0 does not imply the Rainbow Ramsey's theorem. \end{prop}
\begin{proof} Joseph Miller has shown that the Rainbow Ramsey's theorem is equivalent over RCA0 plus some induction to the existence of a d.n.c.\ function relative to ∅′. (Detail needed here on the construction for the forward direction: recursive in a homogeneous set we obtain the function.) By \cite[Exercise 4.3.18]{Nies:book} there is a weakly 2-random set Z that does not compute a 2-fixed point free function, and hence it computes no d.n.c.\ function relative to ∅′. Construct the model \+M⊨W2R0 from Z as above. Then Rainbow Ramsey's theorem fails in \+M.
\end{proof}
Weak Demuth randomness versus \mathtt{WKL}
\begin{definition}
A Δ20 function f is ω-c.e.\ if there is a computable function h such that h(n) bounds the number of changes in a computable approximation to f(n).
A Demuth test is an effective sequence \seq{\+ U_n} of effectively open (Σ10) subsets of Cantor space such that:
1. For all n, the measure λ(\+Un) of \+Un is bounded by 2−n; and
2. there is an ω-c.e.\ function mapping n to a Σ10 index for \+Un.
A set (an element of Cantor space) X is captured by a Demuth test \seq{\+ U_n} if X∈\+Un for infinitely many n. A set is Demuth random if it is not captured by any Demuth test.
A set Zweakly passes a test \seq{\+ U_n} if Z∈⋂n\+Un. A set Z is weakly Demuth random if it weakly passes every Demuth test.
\end{definition}
Figueira et al.\ 13 introduced balanced randomness, a notion in between weak Demuth randomness and ML-randomness where the m-th test component \+Um of a test can be ``replaced" at most O(2m) times. This notion is still stronger than Oberwolfach randomness. More generally, for an order function h we say that Z is h- weak Demuth random if it weakly passes each Demuth test where the component \+Um can be replaced at most h(m) times.
It was observed in 3 that the methods of 13 show the following.
\begin{prop} Let Z=Z0⊕Z1 be ML-random. Then Z0 or Z1 is balanced random, and in fact O(r(n)2n)-weak Demuth random for some order function r. \end{prop}
\begin{proof} We use the terminology of 13. If Z0 is ω-c.e.\ tracing then any weak Demuth test (which is given by an ω-c.e.\ function) can be converted into a ML-test relative to Z0. So by van Lambalgen theorem, Z1 is weak Demuth random.
If Z0 is not ω-c.e.\ tracing then by \cite[Thm.\ 23]{Figueira.Hirschfeldt.ea:15} Z0 is O(r(n)2n)-weak Demuth random for some order function r, and in particular, balanced random.
\end{proof}
So weak weak K\"onigs lemma plus sufficient induction implies the axiom for balanced randomness.
\begin{definition} For a computable function h, we say that a set Z is h-c.e.\ if there is a computable approximation such that Z↾n changes at most h(n) times. For instance, each left-c.e.\ set is 2n-c.e. \end{definition}
Such a set is clearly not h-weak Demuth random. So the following ω-model \+M satisfies WKL but not the axiom for weak h-Demuth randomness, for any function h that dominates each function λn.kn , such as h(n)=2n⋅p(n) for some order function p.
\begin{prop} There is an ω-model \+M of WKL such that each set of \+M is superlow and kn-c.e.\ for some k∈N. \end{prop}
\begin{proof} Let \+S(X) be the Π10 class relative to X of sets that are PA-complete in X. Over RCA, the axiom WKL is equivalent to ∀X\+S(X)=∅.
Let \+Q be the Π10 class consisting of the sets Y such that Yi+1∈\+S(⨁k≤iYk) for each i; here Yi={n:⟨i,n⟩∈Y} is the i-th column of Y.
If Y∈\+Q then the Turing ideal generated by the columns of Y determines an ω-model \+M of WKL.
Let X→WX be the c.e.\ operator such that
\bc 2e(2n+1)∈WX⇔ΦeX(n)=1}. \ec
By the superlow basis theorem as stated in \cite[1.8.38]{Nies:book}, but with the operator W instead of the domain of the usual Turing jump J, there is Y∈\+Q such that WY is left-c.e.
Suppose that R=ΦeY. Since WY is left-c.e., R is 22e(2n+1)-c.e., and hence kn-c.e. where k=22e+2. Thus each set of \+M is kn-c.e.\ for some k∈N.
Clearly Y′≤mWY. So Y is superlow.
\end{proof}
10. Carlucci: Bounded Hindman's Theorem and Increasing Polarized Ramsey's Theorem
The following results were proved after reading the paper Effectiveness of Hindman's Theorem
for bounded sums by Dzhafarov, Jockusch, Solomon and Westrick, 10.
The following natural restriction of Hindman's Theorem to sums with a bounded number of terms
was discussed by Blass in 4 and first studied from a Reverse Mathematics perspective
by Dzhafarov et alii in 10.
\begin{definition}[Hindman's Theorem with bounded sums]
HTk≤n states that for every coloring f:N→k there exists an infinite set H
such that FS≤n(H) is monochromatic for f, where FS≤n(H) denotes the
set of all finite sums of at most n distinct members of H.
We denote ∀kHTk≤n by HT≤n.
\end{definition}
The main results in 10 are (1) that HT2≤2 is unprovable
in RCA0 and (2) that HT3≤3 proves ACA0 over RCA0.
\bigskip
The following version of Ramsey's Theorem is introduced in 9.
\begin{definition}[Increasing Polarized Ramsey Theorem]
IPTkn is the following principle: for every f:[N]n→k there exists a sequence
⟨H1,…,Hn⟩ of infinite sets and c<k such that
for all increasing tuple (x1,…,xn)∈H1×⋯×Hn we have f(x1,…,xn)=c.
The sequence ⟨H1,…,Hn⟩ is called increasing p-homogeneous for f.
We denote ∀kIPTkn by IPTn.
\end{definition}
We first prove that HT5≤2 implies IPT22 over RCA0
by a direct combinatorial argument.
\begin{proof}
We use the following notation: for n∈N,
if n=i0⋅3k0+⋯+it⋅3kt with k0<⋯<kt
and i0,…,it∈{1,2},
we denote k0 by λ(n),
kt by μ(n), and i0 by i(n).
The following elementary properties hold (see 10, Theorem 3.1):
(P1) If λ(n)<λ(m) then λ(n+m)=λ(n) and i(n+m)=i(n).
(P2) If λ(n)=λ(m) and i(n)=i(m)=1 then λ(n+m)=λ(n) and i(n+m)=2.
(P3) If λ(n)=λ(m) and i(n)=i(m)=2 then λ(n+m)=λ(n) and i(n+m)=1.
(P4) If μ(n)<λ(m) then λ(n+m)=λ(n) and μ(n+m)=μ(m).
\bigskip
Let f:[N]2→2 be given. Define g:N→5 as follows.
Note that g is well-defined since λ(n)<μ(n) if n is not of the form i⋅3t, i∈{1,2}.
Let H witnessing HT5≤2 for g be an infinite set such that FS≤2(H) is monochromatic under g.
First, the color of FS≤2(H) cannot be 0: the set H cannot contain two terms 3p,3q with p<q
since their sum is not of the form i⋅3r, and it cannot contain two terms 2⋅3p,2⋅3q
with p<q since their sum is not of the form i⋅3r.
Second, for all h,h′∈FS≤2(H), i(h)=i(h′):
strengthened to FS≤2(H) instead of H. Note that this is necessary for its application
just below establishing (P6), and the same is true in the setting of 10, which needs a minor correction.}
i(n)=1 implies g(n)∈{1,2} and i(n)=2 implies g(n)∈{3,4}.
Then also the following property (P6) holds under the assumption that FS≤2(H)
(rather than FS≤3(H), as in 10)
is monochromatic for g: for all k≥0 there is at most
one n∈H such that λ(n)=k. Suppose otherwise as witnessed by h=h′ in H with λ(h)=λ(h′).
Since we also have i(h)=i(h′), it follows that i(h+h′)=i(h)=i(h′), contra (P5).
Hence we can sparsify H (computably) so as to ensure the following
\begin{center}
(Apartness Condition):
if h<h′ are in H then μ(h)<λ(h′).
\end{center}
Assume without loss of generality that H satisfies the apartness condition.
Assume without loss of generality that the value i(h) for h∈H is 1.
Let c∈{1,2} be such that FS≤2(H) has color c under g.
Let
H1:={λ(n):n∈H}
and
H2:={μ(n):n∈H}.
We claim that ⟨H1,H2⟩ is increasing p-homogeneous for f.
First observe that, letting H={h1,h2,…}<, we have
H1={λ(h1),λ(h2),…}< and
H2={μ(h1),μ(h2),…}<.
This is so because λ(h1)<μ(h1)<λ(h2)<μ(h2)<… by the apartness condition
and the fact that the color is not 0.
Then we claim that f(x1,x2)=c−1 for every increasing pair (x1,x2)∈H1×H2.
Note that (x1,x2)=(λ(hi),μ(hj)) for some i≤j.
If i=j we have
since FS≤2(H) is monochromatic for g with color c.
Thus, in any case
c=1+f(λ(hi),μ(hj))=1+f(x1,x2).
This shows that ⟨H1,H2⟩ is increasing p-homogeneous of color c−1 for f.
\end{proof}
Discussion
Proposition~ ? should be compared with Corollary 2.4 of 10:
RCA0+BΣ20+IPT22⊢SRT22.
Proposition~ ? has the following corollaries.
\begin{corollary}
Over RCA0, HT5≤2 implies SRT22.
\end{corollary}
\begin{proof}
Dzhafarov and Hirst show that IPT22
implies D22 over RCA0 (Proposition 3.5 in ~9).
Chong, Lempp and Yang have later proved that
D22 implies SRT22 over RCA0 (Theorem 1.4 in 6).
\end{proof}
Since SRT22 implies BΣ20, we also have the following corollary.
\begin{corollary}
HT5≤2 is not provable in WKL0.
\end{corollary}
Also, as Ludovic Patey kindly pointed out to us, IPT22 is known to be strictly stronger than
SRT22: Theorem 2.2 in 7 showed that there is a non-standard model
of SRT22+BΣ20 having only low sets in the sense of the model. Lemma 2.5 in 9
can be formalized in RCA0 and shows that no model of IPT22 can contain only Δ20 sets.
Thus, Proposition~ ? implies that HT5≤2 is
strictly stronger than SRT22.
\bigskip
The proof of Proposition~ ? is easily adapted to show
\bc RCA0⊢∀n(HT2n+1≤2→IPTn2). \ec
Then RCA0⊢HT≤2→IPT2.
On the other hand we know that IPT2→SRT2, where
SRT2 denotes the Stable Ramsey's Theorem for pairs and all colors
(Dzhafarov and Hirst 9, Theorem 3.3).
Finally, it is known that RCA0+SRT2⊢BΣ30
(Cholak, Jockusch and Slaman 33, Section 11.2).
Therefore we also have the following corollary.
\begin{corollary}
Over RCA0, HT≤2 implies BΣ30.
\end{corollary}
The author has been up to now unable to lift the combinatorial argument in the proof
of Proposition~ ? to show that
HTk≤3 implies IPT23, for some k≥2.
Note that by results of 9 and 10 the following holds:
RCA0⊢HT4≤3→IPT23.
\part{Computational complexity theory}
11. Thompson: Symmetric functions can be computed by Boolean circuits of linear size and logarithmic depth
Declan Thompson and Matt Bray, Honour's students from Auckland University, visited the
Research Centre Coromandel in February. Declan worked on Boolean circuits, connecting to the CompSci 750 class on computational complexity which Andr\'e had co-taught in Semester 2, 2015.
\vsp
A function f:{0,1}n→{0,1} is symmetric if its value does not depend on the order of its arguments. For Boolean symmetric functions, this means that the output depends only on the number of 1s in the input. It is not hard to see that given a binary representation of the number of 1s in the input, a Boolean circuit of linear size and logarithmic depth can compute the value of a symmetric function. So it suffices to find an efficient method for obtaining this binary representation from the original input.
Circuits exist which add binary numbers in linear size and logarithmic depth (see, for example, the Krapchenko adder of 43). A n\"aive approach to counting the number of 1s is to treat each input as an individual number and utilise an adding tree. Unfortunately this requires a circuit of more than logarithmic depth. Instead, we will utilise so called ``3-for-2'' adders and finally only one Krapchenko adder.
A full adder is a circuit for calculating the sum of three bits. Figure Fig. 1 gives a construction for a full adder. There are three input bits and two output bits, representing the two bit output. A carry save adder (CSA) utilises a chain of full adders to take three n-bit inputs a,b,c and return two n+1-bit outputs u,v such that a+b+c=u+v. The CSA works by sending sum bits (y1 in Figure Fig. 1) to u and carry bits (y2) to v. Specifically, if the full adder returns y2y1 from ai,bi,ci, then ui=y1 and vi+1=y2. We set un=v0=0. As an example, consider the following sum.
100110
111101
+99101101
0110110=u
1011010=v
x1+x2+x3=y2y1. ⊕ denotes addition modulo 2." loading="lazy" style="max-width:100%">
Figure 1. A full adder. x1+x2+x3=y2y1. ⊕ denotes addition modulo 2.
A full adder has a constant number of gates and a CSA uses a full adder for each bit. Hence a CSA uses O(n) size circuits with depth constant, where n is the number of bits of each input number.
We construct an adder tree for x0,…xn−1 by running CSAs in parallel and then combining their outputs. At the first ``level'', there are 31n CSAs each taking in three 1 bit inputs and returning two 2 bit outputs (4 wires in total). At the second level there are 31n⋅2 total inputs and each CSA takes three inputs, so there are 3132n CSAs. In general, at the jth level there are 3132j−1n CSAs taking three j bit inputs and returning two j+1 bit outputs. Each CSA decreases the number of numbers to add by 1 until we are left with two binary numbers. Hence we require n−2 CSAs.
Logarithmic depth of the adder tree is easy to establish. Each CSA has constant depth and since we combine them in a tree fashion the depth of CSAs is logarithmic. Each CSA has size proportional to the number of bits in the inputs. From this, we can conclude that the size of the adder tree is approximately
\[
O(\frac{1}{3}n\sum_{j=1}^{\lfloor\log n\rfloor}\frac{2}{3}^{j-1}j).
\]
However ∑j=1∞32j−1j=9 and so in fact the adder tree is of size O(n).
Thus we have obtained two binary numbers which add to the total number of 1s in the input, using linear size and logarithmic depth circuits. It is now a simple process to use a linear size, logarithmic depth adder (such as Krapchenko's) to obtain a single binary number, which can then be used to determine the output of an arbitrary symmetric function.
12. Describing ordinals less than $ \varepsilon_0$ by finite trees
Andreas Weiermann, Paul Shafer and Nies discussed in Ghent in March. This discussion connected some well-known facts.
For this note a treeB is an acyclic connected directed finite graph with a distinguished root r. B can be naturally viewed as a finite subset of ω<ω (sequences of natural numbers) closed under initial segments; r is the empty string. If B=r then B is given by a tuple (B1,…,Bn) of trees, where the Bi correspond to the successors of r from left to right.
The ordinal o(B) is defined recursively as follows: let o(r)=0. If B=(B1,…,Bn) then \bc o(B)=∑i=1nωo(Bπ(i)) \ec where π is a permutation of {1,…,n} such that o(Bπ(1))≥…≥o(Bπ(n)).
The normN(α) of an ordinal α<ϵ0 is defined by N(0)=0 and N(γ)=1+N(α)+N(β) if γ has
Cantor normal form ωα+β. Clearly each γ<ε0 has the form o(B) for some tree B, and N(γ) is the number of edges of such a tree.
The ordinal of a tree is a complete invariant for tree isomorphism:
\begin{prop} Let B,C be trees. We have \bc B≅C⇔o(B)=o(C). \ec
\end{prop}
\begin{proof}First suppose that ρ:B≅C. If B=C=r then o(B)=o(C)=0. Otherwise B=(B1,…,Bn), C=(C1,…,Cn) and ρ:Bi≅Cσ(i) for σ∈Sn. Inductively we have o(Bi)≅o(Cσ(i)). Choose π∈Sn such that o(Bπ(1))≥…≥o(Bπ(n)). Then o(Cσ(π(1)))≥…≥o(Cσ(π(n))). Therefore o(B)=o(C).
Now suppose α=o(B)=o(C). If α=0 we have B≅C trivially. Otherwise write α in Cantor normal form ∑i=1nωβi where β1≥…≥βn. Since CNF is unique we have B=(B1,…,Bn), C=(C1,…,Cn) with βi=o(Bπ(i))=o(Cθ(i)) for π,θ∈Sn. This shows that B≅C.
\end{proof}
The number of ordinals α with N(α)=n is asymptotically (2.95)nn−1.5 by a result of Weiermann. The number of trees with n edges is (n2n)/(n+1) (Catalan number), which is asymptotically 4nn−1.5/π (much larger).
A tree B is canonical if B is a root, or B=(B1,…,Bn) for canonical trees Bi such that o(B1)≥…≥o(Bn). Clearly each ordinal less than ϵ0 is o(B) for a unique canonical tree. Isomorphism and canonization is in LOGSPACE by a result of Aho, Hopcroft and Ullman. Also see Buss 1995 where algorithms in the smaller class ALOGSPACE are given.
\begin{question} How can one generate a random ordinal with given norm n using poly(n) steps and the appropriate number of nlog2(2.95) of random bits? \end{question}
This amounts to generating a random canonical tree with n edges.
13. Nies and Scholz: Grothendieck's constants
(Written by Nies after some discussion with Volkher Scholz, who works at U Gent in the research group of Prof. Verstraete, and visited Auckland in April.)
Let F be one of the fields R,C. Choose scalars from F. A.\ Grothendieck proved in 1953 that there are positive constants KGF as follows.
Let C=\seq{\gamma_{i,k}} be an n×n matrix such that
i,k∑γi,kaibk≤isup∣ai∣ksup∣bk∣
for each scalars ai,bk. Then for each Hilbert space H over F, and vectors xi,yk∈H (1≤i,k≤n)
\[ \sum_{i,k} \gamma_{i,k} \la x_i, y_k \ra \le K_G^\mathbb F \sup_i ||x_i|| \sup_k ||x_k||. \]
See the reprinted paper~19. In (Eq. 1) we may assume that ∣ai∣=∣bk∣=1 because for fixed C the inequality describes a convex set, so it suffices to look at its extreme points. Given the matrix C as an input, it is known, that the condition in NP-hard. Say for R the problem Max-Cut can be reduced to it (which asks given a graph whether one can partition the set of vertices into two sets so that the number of crossing edges is above a threshold). Easy matrices C satisfying the condition are: n−1I, or the one where each γi,k equals n−2.
We can get away with finite-dimensional Hilbert spaces. However the dimension of H must be unbounded. E.g the value of KGR for dimension 2 is 2.
Interestingly, G's work is closely related to, but predated the Bell inequality (1964). The transition from a problem in real analysis to the setting of Hilbert space corresponds to the transition from classical to quantum physics. The real Grothendieck constant can be viewed as an upper bound on the possible violation of Bell's inequality in a quantum system.
The precise values of the constants are not known. We know that (see 34)
\[ 1 < K_G^{\mathbb C} < K_G^\RR < 1.782.\]
Raghavendra and Steurer \cite[Thm 1.3]{Raghavendra.Steurer:09} prove that KGR is a computable real, and in fact computable up to precision η>0 in time proportional to exp(exp(O(η−3)). No surprise we still don't know what its value is.
\part{Group theory and its connections to logic}
14. Doucha and Nies: Primitive group actions in the setting of Polish Spaces
Michal Doucha and Nies worked at the RCC in 2014/2015.
\begin{definition}
Let G be a Polish group and X a Polish G-space with all orbits dense.
(G,X) is called imprimitive if there exists a closed proper subset D⊆X such that for every g∈G either g⋅D=D or g⋅D∩D=∅ and moreover, D intersects some orbit in at least two elements. I.e., ∃x=y∈D∃g∈G[g⋅x=y]. The set D is called a closed domain of imprimitivity. Otherwise, (G,X) is called primitive.
\end{definition}
Given an action G↷X, we say that an equivalence relation E on X is G-invariant if for every g∈G and every x,y∈X we have xEy↔g⋅xEg⋅y. Equivalently, g⋅[x]E=[g⋅x]E for each g∈G and x∈X.
\begin{prop}
Given a Polish group G and a Polish G-space X with all orbits dense, TFAE:
\bi \item[(i)] (G,X) is imprimitive \item[(ii)] there exists a G-invariant smooth equivalence relation E on X other than idX or X2, with all equivalence classes closed, such that some equivalence class intersects some orbit in at least two elements.
\item[(iii)] as in (ii) but without the restriction to smoothness.
\ei \end{prop}
\begin{proof}
(iii)→(i) Let D=[x]E be an equivalence class of E that intersects some orbit in at least two points. We claim that D is a closed domain of imprimitivity. It is clearly closed and properly contained in X. For each g∈G, if gxEx we have gD=[gx]E=D. Otherwise gD∩D=∅.
\n (i)→(ii). Let D be a closed domain of imprimitivity. Let \bc H={h∈G:h⋅D=D}. \ec Clearly, H is a closed subgroup of G. Since every orbit in X is dense and D is a proper subset, H is a proper subgroup of G.
Let us define a relation E on X. For x,y∈X we define \bc xEy↔∃g∈G[g−1⋅x∈D∧g−1⋅y∈D. \ec We shall prove that E is a smooth G-invariant equivalence relation with closed classes such that some class intersects some orbit in at least two elements.
Since for every g∈G the map x→g⋅x is a homeomorphism of X we have that for each g∈G the set g⋅D is also closed. Denote by X/D the set {g⋅D:g∈G}. We claim for every F1=F2∈X/D we have F1∩F2=∅. Indeed, write Fi as gi⋅D for gi∈G, where i∈{1,2}. If g1⋅D∩g2⋅D=∅, then D∩(g1−1⋅g2)⋅D=∅. Thus by assumption (g1−1⋅g2)⋅D=D, so g1⋅D=g2⋅D, a contradiction. It follows that X/D is the set of E-classes. In particular, E is an equivalence relation with each equivalence class being closed and the E-class D intersects by assumption some orbit in at least two elements.
Consider the quotient G/H consisting of left cosets of H with the quotient topology. It is a folklore fact that this is a Polish space metrizable by the metric δ defined for any g1⋅H,g2⋅H as the Hausdorff distance \bc δ(g1⋅H,g2⋅H)=inf{dG(h1,h2):h1∈g1⋅H,h2∈g2⋅H}, \ec where dG is some compatible right-invariant metric on G. See for example 16 for details. Let us define the map ϕ:X→G/H as follows: \bc ϕ(x)=g⋅H if g−1⋅x∈D. \ec This is well-defined since H fixes D. We now claim that ϕ is a Borel reduction of E into id(G/H). This will show that E is smooth.
To show that it is a reduction, pick some x,y∈X. Suppose that xEy. Then by definition there is g∈G such that g−1⋅x and g−1⋅y lie in D, thus ϕ(x)=ϕ(y)=g⋅H. On the other hand, if ϕ(x)=ϕ(y)=g⋅H, then g−1⋅x and g−1⋅y lie in D.
It remains to check that ϕ is Borel. We show that ϕ factorizes through X/D as ψ∘π, where π:X→X/D is the canonical projection and ψ:X/D→G/H sends g⋅D to g⋅H. We note that a set U⊆X/D is open if and only if ⋃U is open in X. Then we show that ψ is continuous (even open) and ψ is a bijection whose inverse ψ−1 is continuous, that suffices.
That π is continuous (and open) follows directly from the definition of the topology on X/D. Also, it is clear that ψ is a bijection. We check that ψ−1 is continuous. Let U⊆X/D be an open neighbourhood of some g⋅D. Pick arbitrarily some x∈D. Since ⋃U is an open neighbourhood of x and the group action is continuous there exists an open neighbourhood V of g such that for every h∈V we have h⋅x∈⋃U. We have that VH=V⋅H is an open neighbourhood of g⋅H in G/H and we claim that ψ−1(VH)⊆U. This is immediate. Any element of VH is of the form h⋅H for some h∈V and thus sent by ψ−1 to h⋅D. We have that h⋅x∈⋃U and since ⋃U is E-invariant we have that h⋅D⊆⋃U, thus h⋅D∈U.
\end{proof}
\begin{prop}
Let G be a Polish group and X a Polish G-space with all orbits dense. Suppose that for any x∈X the stabilizer Gx is a maximal closed subgroup of G. Then (G,X) is primitive.
\end{prop}
\begin{proof}
Suppose that (G,X) is imprimitive, so there exists a closed domain of imprimitivity D⊆X. Let H={h∈G:h⋅D=D}. H is clearly a closed subset of G. Moreover, since D is a closed domain of imprimitivity we have that H is a group. Let x∈X be such that we have ∣D∩G⋅x∣≥2. We may suppose that x∈D. We have that Gx≤H. We shall show that Gx<H<G and that will be a contradiction with the maximality of Gx. By assumption there exists h∈G∖Gx such that h⋅x∈D. Since D is a domain of imprimitivity, so for every g∈G we have either g⋅D=D or g⋅D∩D=∅, we must have that h⋅D=D and thus h∈H. We have shown that Gx<H. On the other hand, D is a proper closed subset of X and since the orbit of x is dense, there exists g∈G such that g⋅x∈/D and thus g⋅D∩D=∅ and g∈/H. We have shown that H<G and the proof is complete.
\end{proof}
\n Questions.
\n 1. How about the converse implication in Prop. ~ ??
\n 2. Robinson \cite[7.2.5]{Robinson:82} states that if G is primitive on X, then every nontrivial normal subgroup is transitive. (The latter property is called quasiprimitive by Cheryl Praeger.) Check this in the Polish setting, where the normal subgroup is closed, and we have topological transitivity in that every orbit is dense.
15. Nies and Tent: a sentence of size $O(\log n)$ expressing that a group has $n$ elements
This post is related to Nies' and Tent's article ``Describing finite groups by short first-order sentences" 32. We use the definition logn=min{r:2r≥n}.
In that article we gave a description of any finite group G via a first order sentence of length O(log3∣G∣). Here we want to express that the group has size n by a first-order sentence of length O(logn). This will also yield a new way to describe the finite simple
groups in length O(logn), still relying on CFSG but not relying on the short presentations in 20
This work happened in March 2016 at UCLA, after some preliminary work of Nies with the honour's student Matthew Bray. At the BIRS permutation groups meeting Nov 13-18, Csaba Schneider and David Craven provided the crucial references needed to distinguish by short first order sentences the few examples of non isomorphic simple groups of the same size.
\begin{thm} For each n there is a sentence ϕn in the first order language of groups such that ∣ϕn∣=O(logn) and for each group G,
\bc G⊨ϕn⇔∣G∣=n. \ec \end{thm}
We first provide some necessary facts. We use \cite[Lemma 2.1]{Nies.Tent:17}:
\begin{lemma}
For each positive integer r, there is an existential formula θr(g,x) in the first-order language of monoids L(e,∘), of length O(logr), such that for each monoid M,
M⊨θr(g,x) if and only if xr=g.
\end{lemma}
In particular, we can express that a group G has exponent dividing r using O(logr).
The following variant is also needed.
\begin{lemma}
For each positive integer k, there is a formula ψr(y,x) in the first-order language of monoids L(e,∘), of length O(logr), such that for each monoid M,
M⊨ψr(g,x) if and only if xi=g for some i with 0≤i≤r.
\end{lemma}
\begin{proof} Let ψ1(y,x)≡y=1∨y=x. Recursively define
\begin{eqnarray*} \psi_{2k}(y,x) & \equiv & \ex u,v [ y = uv \land \fa z. (z=u \lor z=v) \psi_k(z,x)] \\
\psi_{2k+1}(y,x) &\equiv & \ex u,v [ (y = uv \lor y = uvx) \land \fa z. (z=u \lor z=v) \psi_k(z,x)]
\end{eqnarray*}
Clearly ψr works as required. Further, ∣ψr∣=O(logr).
\end{proof}
We next provide an easy fact on p-groups (which is not first order at this stage).
\begin{fact} Suppose L is a p-group. Then ∣L∣≤pr⇔
∃x1,…,∃xr∈L∀y∈L
∃a1,…,ar[0≤ai<p∧y=i∏xiai].
\end{fact}
\begin{proof} The implication ⇐ is immediate.
For the implication ⇒, we use induction on r. The base case r=1 is obvious since L is trivial or cyclic of order p. Now suppose r>1 and the implication holds for r−1. If L is non-trivial, pick xr in the centre of order p. By inductive hypothesis for L/N where N=⟨xr⟩, we can choose x1,…,xr−1∈L such that statement holds in L/N via xiN, 1≤i<r. So for each y∈L, we have
yN=i=1∏r−1(xiN)ai=i=1∏r−1(xi)aiN
for some ai with 0≤ai<p. Therefore there is ar with 0≤ar<p such that y=∏ixiai, as required. \end{proof}
\begin{lemma} For k=pr, p prime, r∈N there is a sentence βk of length O(logk) such that G⊨βk iff G has a subgroup of size k. \end{lemma}
\begin{proof}
We express (⋄) by a first-order sentence of length O(logk) via the formulas in Lemma~ ?:
\begin{eqnarray} \chi_k(y; x_1, \ldots, x_r) & \equiv & \ex s_0, \ldots, s_r \\ && [ s_0 = 1 \land s_r=y \land \bigwedge_{i=1}^r \ex v \, ( \psi_{p-1} (v, x_i) \land s_i = s_{i-1}v)].\end{eqnarray}
The length of ∣χk∣ is O(rlogp)=O(logk).
Given a group G and x=x1,…,xr∈G, write Uxk={y∈G:G⊨χk(y;x)}.
The sentence βk expresses that there is x=x1,…,xr such that Uxk is a subgroup of exponent dividing k, and r is optimal, namely, there is no y=y1,…yr−1 such that Uyk/p=Uxk.
If G has a subgroup L of size k then G⊨βk by Fact~ ?. Now suppose G⊨βk via x1,…xr∈G. Then L=Uxk is a subgroup of G of size k.
\end{proof}
\begin{proof}[Proof of Thm.\ ?] Using Lemma~ ? we can express that the group G has exponent dividing n. In particular, only prime factors of n can occur in the order of G.
Suppose n=∏i=1mpiri for prime numbers p1,…,pm. We express using Lemma~Eq. 2 for each i≤m that there is a Sylow subgroup of size piri. For each i this takes length O(log(piri)) with the O-constant independent of i. So the resulting sentence has length O(logn).
\end{proof}
It would be interesting to find sentences as in Theorem~ ? with a bounded number of quantifier alternations.
Next we express in logarithmic length that a group is simple. We use \cite[Lemma 2.3]{Nies.Tent:17} on generation. The notation is adapted slightly.
\begin{lemma}
For each positive integers k,v, there exists a first-order formula αkv(g;z1,…,zk) of length O(k+logv) such that for each group G of size at most v, G⊨αkv(g;z1,…,zk) if and only if g∈⟨z1,…,zk⟩.
\end{lemma}
Given a group G of size at most v, we write Lkv(z)={y∈G:G⊨αkv(y;x)} in case this is a subgroup.
Every finite group has a generating set of logarithmic size. So a group G of size at most v is simple iff
\bc G⊨∀z1,…,zk[Lkv(z)⊲G→(Lkv(z)={e}∨Lkv(z)=G)], \ec
where k=logv.
One can use these facts to give a new type of first-order description of finite simple groups in logarithmic length. First one says what the size of the groups is, and that it is simple. A finite simple group is determined by its size, with the exception of \bi \item PSL3(4) which has the same size as Alt8 without being isomorphic to it, and \item the groups Bn=PΩ2m+1(q) and
Cm=PSp2m(q), q an odd prime power, m>2, which have the same size 21qm2∏i=1m(q2i−1) without being isomorphic. \ei (See
http://mathoverflow.net/questions/107620/non-isomorphic-finite-simple-groups for background.)
The exceptional cases above can be distinguished by the fact that the nonisomorphic groups of the same size have different numbers of conjugacy classes of involutions, and that the number of these conjugacy classes is logarithmic in the size. Firstly, in PSL3(4) all involutions are conjugate, while in A8 there are two conjugacy classes, namely (12)(34) and (12)(34)(56)(78). Next, in Bm there are m classes, in Cm for m odd there are (m+1)/2 classes and for m even there are m/2+1 classes. For the latter, see
\cite[Table 4.5.1, p.\ 172]{Gorenstein.ea:98}.
To read this table, note that classes in the simple group are the coset `1', diagonal involutions (outer automorphisms of the simple group) are labelled `d'. The notation 1/d [condition] means 1 if condition holds, d if condition does not hold. (Thanks to David Craven for pointing out the reference and explaining this.)
We note that \cite[Lemma 2.5]{Kimmerle.etal:90} shows that the number of involutions of Bm, Cm also differs for m>2. This could also be used. (Thanks to Csaba Schneider for this reference.)
16. Melnikov and Nies: A computable compact abelian group such that the Haar measure is not computable
Melnikov and Nies worked at the Research Centre Coromandel in June.
Recall a computable topological space X is given by a sequence of basis sets \seq {B_n} \sN n such that for every two such sets Bi,Bk we can uniformly represent Bi∩Bk as an effective union of basic sets. Each computable metric space is also a computable topological space with the basis given by the Bδ(p) for δ∈Q+ and p a special point.
We say that a Borel measure μ on X is computable if μ(Bi) is uniformly left-c.e. in i (if boundaries of open sets are null we could as well require that is it uniformly computable).
A computable topological group is a group G that is also a computable topological space, in such a way that the group operations are effectively continuous.
Recall that every separable compact group has a unique translation invariant probability measure, called the Haar measure.
\begin{thm} There is a computable compact abelian group such that the Haar measure is not computable. \end{thm}
\begin{proof}
Let K denote the halting problem with effective enumeration \seq{K_s}; we may assume that K2=∅. We first give uniformly in e a presentation of a discrete cyclic group Ge such that the Haar measure on Ge is not uniformly computable.
For a real θ let [θ]=e2πiθ. The distance between to points on the circle is the usual shortest arc length.
We define a computable real v=ve uniformly in e; [ve] will be a generator of Ge seen as a subgroup of the circle group. At stage s, if e∈Ks, define vs=21+2−s. If e∈Ks∖Ks−1 define vt=vs−1 for all t≥s.
The special points of Ge are the uniformly computable reals given by the Cauchy name \seq{i v_{s+i}}_{\sN s}. If e∈K then Ge={[0],[1/2]}; if e∈K then ∣Ge∣≥8.
The discrete topology on Ge is uniformly computable: as an effective basis take the sets Ge∩Bδ([ive]) for δ∈Q∩(0,1/2].
Let μe be Haar measure on Ge with the discrete topology. Clearly by the translation invariance of μe we have e∈K↔μe(B1/8(1))>1/4. So μe is not uniformly computable.
Now let G=∏eGe topologized with the product topology which is compact and effective with the usual product basis. Let pe:G→Ge be the projection onto Ge which is computable uniformly in e. If the Haar measure on G is computable then the image measure pe(μ) on Ge is uniformly computable. However, μe=pe(μ) by uniqueness of Haar measure, contradiction.
\end{proof}
17. Fouche and Nies: computable profinite groups
Willem Fouch\'e and Nies went on a 1-week retreat near Port Elizabeth, South Africa, and before and after worked at Unisa Pretoria. As one topic they studied randomness in computable profinite groups.
Background on profinite groups
A separable compact group G is called profinite if G is the inverse limit
G =\varprojlim_n \seq {G_n, p_n}\sN n
of a system of discrete finite groups
→pnGn→pn−1Gn−1→…p2→G1.
The inverse limit is determined up to isomorphism by the universal property formulated in terms of category theory. For a concrete instantiation, it can be seen as a closed subgroup U of the direct product ∏nGn consisting of the functions α such that pn(α(n+1))=α(n) for each n>0.
We may assume that the maps pn are onto after replacing Gn by its subgroup of elements such that all the iterated pre-images under the maps pi are defined. This corresponds to pruning a tree by removing dead ends.
\begin{remark}[Haar measure] Given G as an inverse limit of an onto system, the Haar probability measure μ can be concretely defined as follows. Let qn:G→Gn be the natural projection. A clopen set C of G has the form C=qn−1(F) for a finite set F⊆Gn. By definition μ is translation invariant, so μ(C)=∣F∣/∣Gn∣. As the clopen sets form a basis this determines the measure on all the Borel sets of G.
\end{remark}
Completion
The definition below is taken from \cite[Section 3.2]{Ribes.Zalesski:00}.
Let G be a group, \+V a set of normal subgroups of finite index in G such that U,V∈\+V implies that there is W∈\+V with W⊆U∩V. We can turn G into a topological group by declaring \+V a basis of neighbourhoods (nbhds) of the identity. In other words, M⊆G is open if for each x∈M there is U∈\+V such that xU⊆M.
\begin{definition} The completion of G with respect to \+V is the inverse limit
G\+V=U∈\+VlimG/U,
where \+V is ordered under inclusion and the inverse system is equipped with the natural maps: for U⊆V, the map pU,V:G/U→G/V is given by gU↦gV.
\end{definition} The inverse limit can be seen as a closed subgroup of the direct product ∏U∈\+VG/U (where each group G/U carries the discrete topology), consisting of the functions α such that pU,V(α(gU))=gV for each g. Note that the map g↦(gU)U∈\+V is a continuous homomorphism G→G\+V with dense image; it is injective iff ⋂\+V={1}.
If the set \+V is understood from the context, we will usually write G instead of G\+V.
Free profinite groups
\begin{definition} Let Fk be the free profinite group in k generators x0,…,xk−1 (k<ω). \end{definition} Clearly, Fk is the profinite completion of the abstract free group on k generators with respect to the system of all subgroups of finite index. Any topologically finitely generated profinite group can be written in the form \[ \widehat F_k / R\]
for some k and a closed normal subgroup R of Fk.
\begin{definition} Let Fω be the free profinite group on a sequence of generators x0,x1,x2… converging to 1 \cite[Thm.\ 3.3.16]{Ribes.Zalesski:00}. \end{definition}
Thus, Fω is the completion in the sense of the previous subsection of the free group Fω on generators x0,x1,… with respect to the system of normal subgroups of finite index that contain almost all the xi. Any profinite group G has a generating sequence \seq{g_i}\sN i converging to 1. This is easy to see using coset representatives for a descending sequence of open normal subgroups that form a fundamental system of nbhds of 1G. (Also see \cite[Prop. 2.4.4 and 2.6.1]{Ribes.Zalesski:00}.) By the universal property of the completion, the map from the abstract free group induced by xi→gi extends to a continuous epimorphism Fω→G. So G can be written in the form \[ \widehat F_k / R\]
where R is a closed normal subgroup of Fk.
``Almost everywhere" theorems in profinite groups
\begin{thm}[Jarden; see 15, 18.5.6] Let G=Gal(Qˉ/Q) be the absolute Galois group of Q.
For almost all tuples σ=(σ1,…,σe)∈Ge, the closed subgroup of G topologically generated by σ, is a free profinite group of
rank e. \end{thm}
A group G is called small if it has only finitely many subgroups of each index. Each small residually finite (r.f.)group is hopfian, namely, every epimorphism α:G→G is an isomorphism. (Proof: let Vn be the intersection of subgroups of index ≤n, and check that α(Vn)=Vn for each n.) If g∈kerα and g=1 then g∈Vn for some n, so α(g)=1 as well.)
Every f.g.\ profinite group is small and r.f., and hence hopfian. It follows that σ above actually freely topologically generates G.
A field L is PAC (pseudo-algebraically closed) if every (irreducible) variety over L has a point in L. Besides algebraically closed fields, examples of PAC fields are the algebraic extensions L of Fq with ∣L:Fq∣=ω. See 15 for background. A field L is ω-free if Gal(L) is topologically isomorphic to F^ω.
\begin{thm}[Jarden, see Thms 18.6.1 and 27.4.8 in 15] Let G=Gal(Q) be the absolute Galois group of Q.
For σ=(σ1,…,σe)∈Ge let Lσ=Q[σ] denote the maximal Galois extension of Q contained in the fixed field of σ; equivalently, Lσ is the fixed field of the normal closure of σ.
For almost all tuples σ, Lσ is PAC and ω-free.
\end{thm}
Jarden and Lubotzky 25 study a related setting, namely G=F^n.
\begin{thm}[Jarden and Lubotzky, Thm.\ 1.4 in 25] Let G=F^n for finite n≥2. For almost all tuples σ=(σ1,…,σe)∈Ge, the closed normal subgroup they topologically generate either has finite index or is a free profinite group of
rank ω. The second case holds for all σ if e<n, for almost all σ if e=n, and for a set of σ with positive measure if e>n. \end{thm}
The algorithmic theory
This section has benefitted from discussions with A.\ Melnikov.
Effectiveness conditions on profinite groups
\begin{definition}[Smith~41] \ \bi \item[(i)] A profinite group G is called co-r.e. if it is the inverse limit of a computable inverse system ⟨Gn,pn⟩ of finite groups (i.e.\ the groups Gn and the maps pn between them are uniformly computable). Equivalently, the subgroup U above is a Π10 subclass of ∏nGn. \item[(ii)] G is called computable if, in addition, the maps pn can be chosen onto. In other words, the set of extendible nodes in the tree corresponding to U is computable. \ei\end{definition}
Absolute Galois groups
Let K be a computable field. Then the algebraic closure K has a computable presentation. (Qˉ has a unique one, i.e.\ is autostable, by a result of Ershov.)
Suppose in addition that K has a splitting algorithm (for polynomials in one variable), i.e.\ one can decide whether a polynomial is irreducible. An example of such a field is Q. Then K has a computable presentation so that the K viewed as a subset of K is decidable \cite[Lemma 6]{Rabin:60}.
Also, the absolute Galois group of K is computable. To show this, intuitively, one builds a computable chain K=L0≤L1≤… of finite Galois extensions of K with union Kˉ. The computable inverse system is given by the groups Gn=Gal(Ln/K) where the projection pn:Gn+1→Gn is given by restricting ϕ∈Gal(Ln+1/K) to Ln.
Computable profinite groups that are completions
Suppose G is a computable group, and the class \+V in Definition~ ? is uniformly computable in that there is a uniformly computable sequence \seq{R_n} such that \+V={Rn:n∈N}. Suppose further that W above can be obtained effectively from U,V. Then there is a uniformly computable descending subsystem \seq {T_k} of \seq {R_n} such that ∀n∃kTk≤Rn. Since we can effectively find coset representatives of Tn in G, the inverse system \seq {G/T_n} with the natural projections Tn+1a→Tna is computable. So G\+V is computable.
The criterion above is satisfied by Fk and Fω with the systems of normal subgroups introduced above. Thus their completions F^k and F^ω are computable profinite groups.
\begin{lemma} Let G be k-generated (k≤ω). Then G is computable [co-r.e.] iff G=F^k/N for some computable normal subgroup N (Π10 N). \end{lemma}
Computability of Haar measure
We use the notion of a computable probability space by Hoyrup and Rojas 23.
\begin{lemma} Let G be computable profinite group. Then μG, the Haar probability measure on G, is computable. \end{lemma}
\begin{proof} The inverse system ⟨Gn,pn⟩ is computable. So for a clopen set C=qn−1(F) as in Remark ?, given by the parameters n and F, we can compute the measure. This suffices. \end{proof}
\begin{remark} Here is a more concrete description of the Haar measure. As before qn:G→Gn is the natural projection. We also assume that G1 is trivial. We write V_n =\ker {q_n. For each
n we can effectively determine kn=∣Vn:Vn+1∣ and a sequence \seq{ g^{(n)}_{i}}_{i\lt k_n} of coset representatives for Vn+1 in Vn such that g0(n)=1.
Let T be the tree of strings σ∈ω<ω such that σ(i)<ki for each i<∣σ∣. For ∣σ∣=n we have a coset of Vn in G
Cσ=gσ(0)(0)gσ(1)(1)…gσ(n−1)(n−1)Vn.
The clopen sets Cσ form a basis for G. In this way G is naturally homeomorphic to [T] where the identity element corresponds to 0ω. The Haar measure is the usual uniform measure on [T]. }\end{remark}
Randomness notions defined via algorithmic tests
Let G be a computable profinite group. Given that the Haar measure μ on G is computable, the usual randomness notions defined via algorithmic tests, or effectively descriptive set theory tests, can be applied.
The usual question is: how strong a randomness notion on a group element g suffices for an ``almost everywhere" properties to hold for g?
A point in a computable measure space is Kurtz random (or weakly random) if it is in no Π10 null class. For Jarden's Thm.\ ?,and at least the first part of his Thm.\ ?, this rather weak randomness notion is sufficient. If the underlying topological space is effectively homeomorphic to Cantor space, then any weakly 1-generic point (i.e., in every dense Σ10 set) is Kurtz random. As this applies to the setting of profinite groups at hand, the points for which Jarden's results hold are also comeager.
\begin{thm}[effective form of Jarden's Thm.\ ? for Q] Let G=Gal(Q) be the absolute Galois group of Q.
Let σ=(σ1,…,σe)∈Ge be Kurtz random. The closed subgroup generated by σ is a free profinite group of
rank e (freely generated by σ). \end{thm}
Here is a sketch why this is true. (For a full proof, thorough understanding of Jarden's result would be needed, which is hard work because of the long chain of dependencies and heavy notation leading up to \cite[18.5.6]{Fried.Jarden:06}.) All item numbers refer to 15.
Two extensions L1,L2 of a common field K (tacitly assumed to be contained in a common field) are called linearly disjoint if whenever a tuple from L1 is linearly independent over K, it remains linearly independent over L2. By Lemma 2.5.1.\ this is symmetric.
A sequence of extensions L1,L2,… is linearly disjoint if Lj+1 is l.d.\ from the compositum L1…Lj for each j. Given k, Cor.\ 16.2.7.\ builds such a sequence of Galois extensions for K=Q such that for each n we have Gal(Ln/Q)≅Sk via some isomorphism ρn. The sequence of fields \seq {L_n} is uniformly computable, as can be derived from the proof (hopefully).
By 18.5.1.\ the linear disjointness implies that the absolute Galois groups Gal(Ln)≤Gal(Q) are μ-independent; recall that μ is the Haar measure on G=Gal(Q). More generally, by 18.5.2, for e≥1, if for each n one picks a coset Cn of Gal(Ln)e in Ge, the Cn are μe-independent.
Now to conclude the argument, we want to show that each finite group R generated by e elements is a quotient of
the closed subgroup ⟨σ⟩≤G generated by σ, as this suffices to show freeness. Embed R into Sk for k sufficiently large, and let π1,…,πe be the images of the generators of R under this embedding.
For each n we have a natural onto homomorphism G→Gal(Ln/Q) given by restriction to Ln (note that Ln, being a normal extension of Q, is preserved under automorphisms of Qˉ). So we can effectively pick a coset Cn of Gal(Ln)e in Ge that maps to ⟨π1,…,πe⟩. Since the Ln are independent, these cosets are independent, and each has measure 1/(k!)e. Hence, by Borel-Cantelli their union has measure 1. The union is Σ10 and hence contains the Kurtz random σ. This shows that R is a quotient of ⟨σ⟩ as required.
\begin{thm}[effective form of the first part of Jarden's Thm.\ ? for Q] In the setting of Thm. ?, recall that for an automorphism σ∈Gal(Q), Lσ is the fixed field of the normal closure of σ. If σ is Kurtz random, then Lσ is PAC. \end{thm}
\begin{proof} We first show that Lσ is uniformly computable from (a code for) σ. For x∈Q to be in Lσ, it suffices that each conjugate τ−1στ fixes x, or equivalently σ(y)=y for each y in the orbit of x under the action of Gal(Q). This orbit consists of all the conjugates of x, and can be computed from x.
By Jarden's theorem and the fact that a Kurtz random is in every Π20 conull set, it now suffices to show that the PAC subfields K of Q form a Π20 class.
Recall that for a unital ring R, a nonconstant polynomial in R(X1,→Xn) is called irreducible if it cannot be written as a product for two nonconstant polynomials. For a field K, a polynomial in K[X1,…,Xn] is called absolutely irreducible if it is irreducible in K[X1,…,Xn]. We use some facts on PAC fields from \cite[Section 11.3]{Fried.Jarden:06}. \cite[Theorem 11.2.3]{Fried.Jarden:06} implies:
\begin{prop} A field K is PAC if and only if for every absolutely irreducible polynomial f∈K[X,Y], there is a point (a,b)∈K2 with f(a,b)=0. \end{prop}
This yields the required Π20 condition as soon as we can express using a Π10 condition on the coefficients of f that a polynomial f∈K[X,Y] is absolutely irreducible. But irreducibility of f in the polynomial ring R[X1,…,Xn] is a Π10 condition on the coefficients of f for any computable ring R, as one sees directly by inspecting the definition. \end{proof}
\begin{remark} The conditions (1) on page 200 in \cite[Section 11.3]{Fried.Jarden:06} yield a set of sentences in first-order logic expressing that a field is PAC. SK(2,d) denotes the set of polynomials f∈K(X,Y) of degree <d in both X and Y. They say that for each irreducible h∈Q(T), some Π10 condition holds (for each triple of polynomials g1,g2,g3) of bounded degree, something not involving quantifiers fails). It is decidable whether h is irreducible as Q has a splitting algorithm, so we can also get a co-r.e.\ condition on coefficients in this way. \end{remark}
Potential generalisation to Hilbertian fields
A field K is Hilbertian if every finite set of irreducible polynomials in a finite number of variables and having coefficients in K admit a common specialization of a proper subset of the variables to field elements such that all the polynomials remain irreducible (Wikipedia). Hilbert showed that Q has this property (Hilbert's irreducibility theorem). All the classic a.e.\ theorems from 15 mentioned above are stated for any countable Hilbertian field, rather than just for Q. If K is computable and has the effective splitting property, then one can expect that the effective versions hold as well.
18. Rute: On the computability of compact groups
This note covers basic theorems about the computability of Haar measures and profinite groups. The results are due to Jason Rute and were proved after discussions with Nies and Melnikov.
While we could work in the more general context of computable topological spaces, we will only focus here on computable metric spaces (also known as computably presented Polish spaces), since they are well understood.
Recall that a computable metric spaceX is a complete separable metric space (X,d) along with a dense sequence of points (ai) such that the map i,j↦d(ai,aj) is computable. We say X is effectively compact if one can enumerate all Σ10 sets which cover X. It is easy to see that Cantor space is effectively compact. We will need the following well-known properties about effectively compact spaces.
\begin{prop}
Let X be a computable metric space along with a computable sequence An where An is a list of points (a1n,…,akn) such that every point in X is within distance 2−n of some ain. Then X is effectively compact.
\end{prop}
\begin{proof}
Using the double sequence (ain) we can construct a computable onto map f:2N→X. (The details are routine but a bit technical. A similar construction can be found in Simpson \cite[IV.1]{Simpson:09}.) Now, we want to enumerate all effectively open covers of X. That is the same as enumerating all empty Π10 subsets of X. Consider a Π10 set P⊆X. The set f−1(P) is Π10 subset of 2N, and it is empty iff P is empty. Since 2N is effectively compact we will enumerate f−1(P) eventually if it is empty, and then we can use that to enumerate P.
\end{proof}
\begin{prop}
If X is an effectively compact computable metric space and {a}⊆X is a Π10 singleton set, then a is computable. If f:X→X is a function whose graph f⊆X×X is Π10, then f is computable.
\end{prop}
\begin{proof}
Let U be the complement of {a}. Compute a by enumerating covers of the space of the form U∪B where B is a basic open ball of small radius. Similarly, use this method to compute f(x) from x.
\end{proof}
\begin{definition} A computable topological Polish group to be a computable metric space G with a computable group operation and a computable inverse operation.
^2withtheEuclidean(\ell_2)metricandthe\ell_\inftymetricareequivalentwithanynaturalchoiceofdenseset.ThenwecandefineacomputablePolishspaceasthesetofequivalenceclassesofcomputablemetricspaces.Similarly,wecanusethisideatogiveaslightlymorenaturaldefinitionofcomputablePolishgroup,againasequivalenceclasses.Thedownsideofthisapproachisthatweneedtoconstantlyshowthatthepropertiesweareinterestedinarepreservedbythisequivalencerelation.Forexample,iftwopresentationsofaspace\mathbb{X}areequivalent,andonepresentationiseffectivelycompact,thensoittheotherpresentation.Also,iftwopresentationsof\mathbb{X}areequivalent,thensoarethevariouscorrespondingpresentationsofthespaceofBorelprobabilitymeasureson\mathbb{X}$. } \end{definition}
The computable analogue of a compact group is a computable Polish group which is effectively compact.
\begin{fact}
If G is an effectively compact computable metric space with a computable group operation, then the inverse operation is also computable, and therefore G is a computable Polish group.
\end{fact}
\begin{proof}
Notice that the graph of the inverse function {(g,g−1)∣g∈G} is a Π10 set. So the inverse map is computable by Proposition~ ?.
\end{proof}
If X is a computable metric space, then the space of Borel probability measures on X is also a computable metric space. In particular, a Borel probability measure μ is computable if and only if the map f↦∫fdμ is a computable map for all bounded computable functions f:X→R. If X is effectively compact, then so is the space of Borel probability measures on X. For more on the computability of Borel probability measures, see Hoyrup and Rojas 22 or Bienvenu, Gacs, Hoyrup, Rojas, and Shen 2.
\begin{prop}
Let G be an effectively compact computable Polish group. Then the left and right Haar probability measures are computable.
\end{prop}
\begin{proof}
The set of, say, left Haar probability measures is a Π10 singleton set in the effectively compact space of Borel probability measures on X. By Proposition~ ? the left Haar measure is computable.
\end{proof}
\begin{thm}
Let G be a compact computable Polish group for which the (left) Haar probability measure is computable. Then G is effectively compact.
\end{thm}
\begin{proof}
We re-metrize the space G by replacing d(x,y) with the average of d(gx,gy) where the average (the integral) is taken in the Haar measure as g varies across the group. This new metric is computable since d(x,y) is a bounded computable function. (The metric is bounded by the compactness of G.) Now one has a computable G-invariant distance which is equivalent to the original distance.
Now, to show that G is effectively compact in this new metric, it is enough for each rational k, to effectively find a finite set of points a0k,...,an−1k for which every point in G is within distance 2−k of one of these points. Fix k. Using our Haar measure find the measure of a ball of radius 2−(k+1). Call this measure δ. (Since the new distance is G-invariant, all balls of the same radius have the same measure.) Using blind search find a collection of balls B0,...,Bn−1 of balls with radius 2−(k+1) whose union C=B0∪...∪Bn−1 has measure >1−δ. Now, consider any point x not in this union C. It has to be distance <2−(k+1) from the union. Otherwise, there would be a ball centered at x with radius 2−(k+1), and hence measure δ, which is disjoint from the union C. But the union C has measure >1−δ, so this cannot happen. Therefore all points of G are within distance 2−k of the centers of B0,...,Bn−1. This algorithm shows that the space is effectively compact in the new metric. To show it is effectively compact in the original metric, for any finite list of rational balls in original metric, convert it to a list of balls in the new metric. Now, if this list of balls covers the space G, by effective compactness, we will eventually find this out.
\end{proof}
\begin{example}
There is a computable group G isomorphic to a product of finite cyclic groups ΠnGn which is compact but for which the Haar measure is noncomputable.
\end{example}
\begin{proof}
Let h(n) be the characteristic function of the Halting set. Then we will let G=∏nZ2h(n) with the ultrametric ρ(f,g)=inf{2n∣f(n)=g(n)}. This is a computable metric space (but it is not effectively compact). It is also a computable Polish group. The Haar measure of any cylinder set of length n is equal to ∏k<n2−h(n). If we could compute the Haar measure, then we could compute h(n).
\end{proof}
As Section~Section 4 in this year's Logic Blog mentioned, a profinite group is an inverse limit of finite groups. So there exists a descending chain of normal clopen subgroups Ns⊲G which converges to the identity. Then G is the inverse limit of G/Ns. A G is computably profinite.
\begin{thm}
Let G be a profinite effectively compact computable Polish group. Then we can compute a sequence of finite groups Gs such that G is the inverse limit Gs and the corresponding homomorphism hs:G→Gs is computable.
\end{thm}
\begin{proof}
Since G is profinite, we need to find a descending chain of normal clopen subgroups Ns⊲G. Since G is effectively compact, we can enumerate all clopen sets A by finding disjoint covers made up of finitely many open balls B1,…Bn,C1,…,Cm where Bi and Cj are disjoint. We can then use this to enumerate all normal clopen subgroups as follows. Since each clopen set A is both effectively open and closed, the property
\[\forall g\in G\quad gAg^{-1} \subseteq A\]
is Π10 (if the property fails, then search for some g∈G and some a∈A such that gag1 is outside of A) and Σ10 (if the property holds, then wait for an enumeration of balls which cover gAg−1 and which are disjoint from a cover of the complement of A). Therefore, we can enumerate all clopen normal subgroups N⊲G.
Let Ns be the intersection of all clopen normal subgroups enumerated at stage s of the construction (where N0=G). This is also a clopen normal subgroup. Now enumerate all cosets gNs. (These can be enumerated since each coset gNs is also clopen. Also we know when we have enumerated them all since they form an open cover of an effectively compact space.) From this we can compute G/Ns along with the corresponding homomorphism. (If G is finite, then at some stage, G/Ns is isomorphic to G.)
\end{proof}
\part{Metric spaces and descriptive set theory}
19. Nies and Weiss: \\ complexity of topological isomorphism for subshifts
Let Σ be a finite alphabet.
A subshift is a closed subset X⊆ΣZ which is invariant under the shift σ. We consider the complexity of the isomorphism relation (X,σX)≅(Y,σY) where Σ,Δ are finite alphabets and X⊆ΣZ, Y⊆ΔZ are subshifts. To be isomorphic means that there is a continuous bijection θ:X→Y such that θ(σX(z))=σY(θ(z)) for each z∈X. Note that θ is given by the clopen sets θ−1({Z:Z(0)=b}) for b∈Δ, which are of the form ⋃i<k[αi] where αi:[−N,N]→Σ (such a collection of clopen sets is called a block code). So isomorphism is a countable Borel equivalence relation.
J.\ Clemens (Israel J. of Maths, 2009) proved that isomorphism is in fact a ≤B-complete countable Borel equivalence relation.
A subshift is minimal if every orbit of an element is dense; equivalently, every possible pattern (i.e.\ subword of a fixed length of an element of the subshift) occurs in a large enough section of every element of the subshift. By compactness, the length of this section only depends on the pattern. As a consequence, minimality is a Borel property of subshifts. Also, it is sufficient to require the property that patterns re-occur within a distance only dependent on the pattern for one word with dense orbit.
Clemens asked in the paper and in a 2014 talk (available on youtube) the following question:
\begin{question} How complex is the isomorphism relation between minimal subshifts? \end{question}
Gao, Jackson and Seward \cite[Section 9.3]{Gao.Jackson.etal:16} proved that E0 is Borel reducible to isomorphism of minimal subshifts.
\begin{proof} Here is a sketch of a short proof of this fact.
The idea is to build a sequence of blocks
An,Bn of length Ln=(66)n. The construction
is controlled by a fixed element x∈{0,1}N
with the n-stage blocks a function of xi for
1≤i≤n. This sequence of blocks determines a subshift Sx: the allowed patterns of length Ln are the An
and Bn.
The blocks An+1,Bn+1
will be built out of the n-stage blocks in such a way that any bi-infinite sequence formed by concatenating these two
blocks has a unique parsing into blocks of these two types. This
parsing defines for each bi-infinite word \seq {z(i)}_{i \in \ZZ} a unique integer modulo
Ln which indicates the position of z(0) in the block.
Recall that an odometer is a dynamical system that is an inverse limit of periodic rotations. The simplest example is the 2-adic integers with addition by 1. Since Ln+1 is a multiple of Ln, the position of z(0) modulo Ln+1
when reduced modulo Ln gives the position of z(0) in its ``n-block".
This will yield a common odometer as a factor of all the minimal shifts.
Let A0=0 and B0=1. We describe 4 recipes for concatenating A,B:
\bi \item[1.] AB(A4B4)8
\item[2.] AB(A8B8)4
\item [3.] AB(A16B16)2
\item [4.] ABA32B32. \ei
\n Depending upon the value of xn
the An+1,Bn+1 will be formed in two different
ways. If xn+1=1 one uses 1 and 2, otherwise one uses
3 and 4. Assuming that one can recognize A and B, the initial ABA in all
recipes guarantees that the concatenations have a unique parsing.
The minimality is immediate since all four possibilities
AA, AB, BA, BB occur.
Each specfic minimal system has its own
collection of the two types of blocks, where the nature of the blocks
up to level n depend only on the first n bits of the control element
from 0,1N. Clearly if x and y agree from some point on
there is a finite block code that will map one shift to the other.
If x and y differ infinitely often then no matter what the
length of the code eventually it will pick up the pattern of
repetitions which differ significantly in all 4 recipes.
\end{proof}
Simon Thomas 42 has given a Borel reduction of E0 to a special class of minimal subshifts, the Toeplitz subshifts. A Toeplitz word is a bi-infinite word W such that for n∈Z there is a ``local period" k∈Z such that ∀i∈Z[W(n)=W(n+ik)]. A subshift is Toeplitz if it contains a Toeplitz word with dense orbit. To see that this is minimal, suppose that w is a subword of W, and let r be the l.c.m.\ of the local periods of any symbol in w. Then σr(w) is also a subword of W, for any r∈Z.
Not much beyond that is known so far on the complexity of conjugacy for minimal subshifts.
\part{Higher computability theory/effective descriptive set theory}
20. Yu: $\Pi^1_1$-hyperarithmetic determinacy
Input by Yu.
The following theorem was claimed in 21: the hyperdegrees of a Π11 set with a perfect subset contain an upper cone.
\begin{theorem}[Harrington 21]
Let A⊆2ω is a Π11 set that contains a perfect subset. There is a real z∈2ω so that for any real y≥hz, there is a real x∈A for which x≡hy.
\end{theorem}
The following proof is based on some communications with Leo Harrington. His original idea seem model theoretical. Here is a tree proof.
The following theorem is proved by Martin.
\begin{theorem}[Martin 28]
If A is an uncountable Δ11-set, then for any real y≥hO, there is a real x∈A for which x≡hy.
\end{theorem}
Fix an uncountable Π11 set A throughout in this section.
Since A is Π11, there is a recursive oracle functional
Φ so that
̲\omega." style="color:#cc0000">x\in A \Leftrightarrow \Phi^x codes a well
ordering of ω.
In other words, the binary relation n≤xm if and only if Φx(⟨n,m⟩)=1 is a well ordering over ω. We use n∈Dom(Φx) to denote that there is some m so that Φx(⟨n,m⟩)=1 or Φx(⟨m,n⟩)=1. For a finite binary string σ, we also use <Φσ to denote the finite linear order coded by
Φσ.
Let
̲\omega with or…" style="color:#cc0000">\beta=\min\{\beta\mid |\{ x \mid \Phi^x codes a well
ordering of ω with order type \beta\}|\gt \aleph_0\}.
Since A has a perfect subset, such β must exist.
We fix the β throughout.
We associate a tree T with A by defining (σ,τ)∈T if
and only if
1. σ∈2<ω and;
2. τ is finite order preserving function from Dom(Φσ)
to ordinals.
We always assume that ∣Dom(Φσ)∣=∣σ∣.
(σ0,τ0)⪯(σ1,τ1) if both σ1 and τ1 extends σ0
and τ0 respectively. (σ0,τ0) is at the left of (σ0,τ0)
if 1. for some are m≤min{∣σ0∣,∣σ1∣},
σ0↾m=σ1↾m but σ0(m+1)<σ1(m+1) or
2. for every $\sigma_0\uh
\min\{|\sigma_0|,|\sigma_1|\}=\sigma_1 \uh \min\{|\sigma_0|,|\sigma_1|\}andforsomek$,
τ0(k)<τ1(k) but τ0(j)=τ1(j) for all j<Φσk.
Then x∈A if and only if there is an f so that (x,f) is an
infinite branch of T.
Let Tβ be the tree T restricted to the ordinal
β, i.e. the range of every σ is a subset β+1.
Obviously Tβ∈Lω1β. Moreover, there are
uncountable many infinite branches in Tβ by the definition
of β. Let
̲\omega of orde…" style="color:#cc0000">A_{\beta}=\{x\mid \Phi^x codes a well
ordering of ω of order type \leq\beta\}.
Then Aβ is exactly the collection of reals x for which
there is an f so that (x,f) is an infinite branch through
Tβ.
Obviously Aβ is an uncountable Borel set containing a perfect subset.
Let ω1β be the least admissible ordinal greater than β. Obviously Tβ∈Lω1β.
Case(1): There is a real z so that z\in L_{\omega_1^{\beta} and ω1z=ω1β.}
Then let $B_{\beta}=\{x\mid \Phi^x codes a well
ordering of order type \beta\}\subseteq A_{\beta}bea\Delta^1_1(z)−set.Thenforanyrealx\in B_{\beta},x\geq_h z.RelativizingtheproofofTheorem?toz$, we may have Theorem ?.
Case(2): Otherwise.
Then for any real x∈Aβ, if Φx codes a well ordering of β, then x∈Lω1β.
Fix a recursive enumeration of set theoretical Σ0-formulas {φi(u,v,β)}i∈ω with β as a parameter. Then ω1β is the least ordinal γ>β so that for any i,
Lγ⊨∀u<β∃vφi(u,v,β)→∃w∀u<β∃v∈Lwφi(u,v,β).
We also do a Cantor-Bendixon derivation to Tβ. I.e. T0β=Tβ; and for any stage γ<ω1β and (σ1,τ1)≻(σ0,τ0)∈Tγβ, if
1. either there exists an order preserving (in the <KB sense ) function f∈Lβ so that f:T1β[(σ1,τ1)]→β; or
2. there exists a real x∈Lβ so that {x}={z≻σ1∣∃f≻τ1∀n(x↾n,f↾n)∈Tγβ},
then we let T1β+1=T1β∖[(σ1,τ1)] and claim that (σ1,τ1) is cut off from Tγβ at stage γ.
If γ is a limit stage, then Tγβ=⋂γ′<γTγ′β.
Let
Tω1ββ=γ<ω1β⋂Tγβ.
Obviously Tω1ββ is not empty.
Let T1⊆2ω×ω<ω be a recursive tree so that p[T1]={x∣∃f(x,f)∈[T1]}={x∣x∈Lω1x}.
Since Aβ contains a perfect subset, p[T1]∩Aβ=∅.
\begin{lemma}If x∈p[T1]∩Aβ, then x∈Lω1β and ω1x≥ω1β. Moreover, if Φx codes a well ordering of order type less than β, then x∈Lω1x and ω1x≤ω1β. \end{lemma}
\begin{proof}
Fix a real x∈Aβ.
If Φx codes a well ordering of order type β, then ω1x≥ω1β. So x∈Lω1β.
If Φx codes a well ordering of order type γ less than β, then Aγ is a countable set which is Δ11(z) for any real z with ω1z≥γ. Then x≤hz for any real z with ω1z≥ω1γ. But ω1x≥ω1γ. So x∈Lω1γ and ω1γ=ω1x. Hence x∈p[T1].
\end{proof}
Obviously T2∈Lω1β and [T2] is not empty. Let (x,f,h) be the leftmost infinite path through T2. Then x∈p[T1]∩Aβ and so by Lemma ?, x∈Lω1β+2∖Lω1β. In other words, there must be a master code in Lω1β+2∖Lω1β.
Fix a standard master code z_0 \in L_{\omega_1^{\beta+2}\setminus L_{\omega_1^{\beta}}}.
Now let y0>hz0 be a real.
\begin{definition}
Given a tree S⊂2<ω×α<ω where α is an ordinal, a finite pair (σ,τ)∈S is called a splitting node in S if for any i≤1, there is some γi so that (σ⌢i,τ⌢γi)∈S.
\end{definition}
\begin{definition}
Given an infinite path (x,f)∈[Tω1ββ], a number n and an ordinal γ≤ω1β, we say that γ is correct up to n respect to (x,f) if for any i≤n, (x↾i,f↾i) is a splitting node in Tω1ββ if and only if (x↾i,f↾i) is a splitting node in Tγβ.
\end{definition}
The following lemma is clear.
\begin{lemma}
Suppose that (x,f)∈[Tω1ββ], n is a number and γ≤γ′≤ω1β. If γ is correct up to n respect to (x,f), the so is γ′.
\end{lemma}
The following definition is crucial to the proof. Intuitively we use even parts to code y0 so that we may find a very large stage at which we may witness whether φi(u,v,β) can be satisfied. However we use the odd parts to indicate when the coding stage is finished.
\begin{definition}Given a finite pair (σ,τ)∈Tω1ββ, let (x_{\sigma,f_{\tau })\in [T_{\omega_1^{\beta}}^{\beta}[\sigma,\tau]]} be an infinite path satisfying the following properties:
- If fτ↾(n) is the least ordinal γ so that [Tω1ββ[xσ↾n+1,fτ↾n⌢γ]]=∅; and
- If n is the 2k-th number (in the natural ordering sense) for some k>0 in SPσ,τ={j∣(xσ↾j,fτ↾j)∈[Tω1ββ[σ,τ]]isasplittingnode}, then xσ(n+1)=xσ(n)⌢y0(k); and
- If n is the 2k+1-th number for some k≥0 in SPσ,τ, then xσ(n+1)=xσ(n)⌢0.
\end{definition}
Obviously given any number n and pair (σ,τ)∈Tω1ββ, (xσ,fτ) always exists and fτ∈Lmax{ω1x,ω1β}[x].
\begin{lemma}
Φxσ codes a well ordering of ω with order type β.
\end{lemma}
\begin{proof}
Otherwise, by Lemma ?, x∈Lβ. So by a zig-zag decoding argument over Tω1ββ, y0≤x⊕z0≡hz0, a contradiction.
\end{proof}
\begin{lemma}
If there is a pair (σ,τ)∈Tω1ββ and some stage γ<ω1β so that for any n, γ is correct up to n respect to (xσ,fτ), then xσ≡hy0.
\end{lemma}
\begin{proof}
By the property of (xσ,fτ), fτ∈Lω1xσ[xσ]. We claim that ω1β≤ω1xσ. Otherwise, by Lemma ?, xσ∈Lβ. By by a zig-zag coding over Tγβ[σ,τ], we have that y0∈Lω1β[xσ]=Lω1β , a contradiction to the choice of y0.
So γ<ω1β≤ω1xσ. Then it is clear that, by a zig-zag decoding over Tγβ[σ,τ], we may decode y0 by (xσ,fτ). So y0≤hxσ. Obviously y0≥hxσ. So xσ≡hy0.
\end{proof}
So if the assumption of Lemma ? holds, then the proof of Theorem ? is finished.
\bigskip
From now on, we assume for any pair (\sigma,\tau)\in T_{\omega_1^{\beta}^{\beta} and any ordinal γ<ω1β, there is some number n so that γ is not correct up to n respect to (xσ,fτ).}
\bigskip
Now we turn to the real construction. We will construct an infinite path (x,f)∈Tω1ββ so that y0≡hx. To code y0, we use a zig-zag coding which is performed in Lω1β+1. So the point is show ω1x>ω1β.
We start to construct (x,f) by induction on ω.
At stage 0. Let (σ00,σ01)=(∅,∅)∈Tω1ββ.
At stage s+1. Suppose that (σs0,σs1)∈Tω1ββ has been constructed so that (σs0,σs1) is a splitting node in Tω1ββ (Without loss of generality, we may assume that (∅,∅) is a splitting node in Tω1ββ.).
Substage (1): We code y0(s) at this substage.
Let σs,10 be the shortest finite string so that there is a string σs,11 such that
- [(1)] (σs,10,σs,11)∈Tω1ββ is a splitting node; and
- [(2)] σs,10⪰(σs0)⌢y0(s); and
- [(3)] (σs,10,σs,11) is the leftmost string in {(σs,10,τ)∣(σs,10,τ)∈Tω1ββ}.
Obviously such a pair (σs,10,σs,11) exists.
Substage(2): We try to make sure ω1x>ω1β at this stage. Let (xσs,10,fσs,11)∈Tω1ββ[σs,10,σs,11] be as defined in Definition ?.
Case(2.1). Lω1β⊨∀u<β∃vφi(u,v,β). Then let γs be the least ordinal so that ∀u<β∃v∈Lγsφi(u,v,β). Then by the assumption, we may let ns be the least number n so that
- (xσs,10↾n,fσs,11↾n) is a splitting node in Tω1ββ; and
- n is the 2k+1-th number for some k≥0 in SPσs,10,σs,11={j∣(xσs,10↾j,fσs,11↾j)∈Tω1ββ[σs,10,σs,11]isasplittingnode};
- γs is not correct up to n respect to (xσs,10,fσs,11).
Then let (σs+10,σs+11) be a finite string such that
- [(1)] (σs+10,σs+11)∈Tω1ββ is a splitting node extending (xσs,10↾ns,fσs,11↾ns); and
- [(2)] σs+10⪰xσs,10↾ns⌢1 (we use this to indicate the coding construction at this stage is finished); and
- [(3)] (σs+10,σs+11) is the leftmost string satisfying above property.
Case(2.2). Otherwise. Then there is some u<β so that Lω1β⊨∀v¬φi(u,v,β).
Then by the assumption, let ns be the least number n so that
- (xσs,10↾ns,fσs,11↾n) is a splitting node in Tω1ββ; and
- There is some d∈Dom(Φxσs,10↾n) so that fσs,11↾n(d)=u (remember that fσs,11↾n is a finite order preserving function from Dom(Φxσs,10↾n) to β); and
- n is the 2k+1-th number for some k≥0 in SPσs,10,σs,11;
Since Φxσs,10 codes a well ordering of order type β, such a number ns must exist.
Then let (σs+10,σs+11) be a finite string such that
- [(1)] (σs+10,σs+11)∈Tω1ββ is a splitting node extending (xσs,10↾ns,fσs,11↾ns); and
- [(2)] σs+10⪰xσs,10↾ns⌢1 (we use this to indicate the coding construction at this stage is finished); and
- [(3)] (σs+10,σs+11) is the leftmost string satisfying above property.
This finishes the coding construction at stage s+1.
\bigskip
Let
(x,f)=s∈ω⋃(σs0,σs1).
By the construction, f is an automorphism between Φx and an initial segment of ω1x. By the same proof of Lemma ?, Φx codes a well ordering of ω with order type β and so ω1x≥ω1β. Hence f is an automorphism between Φx and β.
We use a method in 44 to decode the coding construction. We shall x-hyperarithmetically construct an increasing sequence ordinals {αi}\i∈ω so that limiαi=ω1β. Then ω1x>ω1β. Once this is archived, then by a zig-zag decoding, we have that x≥hy0 and so x≡hy0.
\begin{definition}Given a finite increasing sequence {ni}i≤s for some s and an ordinal γ<ω1β, we say that γmatches {ni_i≤s} if all the following facts hold:
- n0=0; and
- For any l≤ns, (x↾l,f↾l) is the leftmost in {(x↾l,τ)∣(x↾l,τ)∈Tγβ}; and
- For any j∈(0,s],
\begin{itemize}
- There is a number l0 which is the least number greater than nj−1 so that (x↾l0,f↾l0) is splitting node in Tγβ; and
- (x↾l0,f↾l0) is the leftmost finite string in {(x↾l0,τ)∣(x↾l0,τ)∈Tγβ}; and
- There is a number l1>l0 so that (x↾l1,f↾l1) is the 2k+1-th number, for some k, in SPx↾l0,f↾l0={j∣(x↾j,f↾j)∈Tγβ[x↾l0,f↾l0]isasplittingnode} so that x≻x↾l1⌢1; and
- Either Lω1β⊨∀u<β∃v∈Lγφi−1(u,v,β) or there is some d∈Dom(Φx↾l1) so that Lω1β⊨∀v∈Lγ¬φi−1(f(d),v,β); and
- nj is the least number greater than l1 so that (x↾nj,f↾nj) is a splitting node in Tγβ.
\end{itemize}
\end{definition}
Intuitively if γ matches {ni}i≤s, then, up to ns, Tγβ is ``quite like Tω1ββ along (x,f)".
\bigskip
Now we start to do the decoding construction.
At stage 0, let α0=0 and n00=0. Claim that 0 is inactive, i is active and ni0 is undefined for any i>0.
At stage s+1, then is is the least i so that i is active. Also, by induction, njs is defined for any j<is.
Case(1). There is a number i′<is so that αs+1 does not match {nj}j≤i′. Let is+1 be the least such i′. Let αs+1=αs+1 and claim ij is active and njs+1 is undefined for all j≥is+1. Moreover, set njs+1=njs for any j<is+1. Go to next stage.
Case(2). Otherwise. Search an ordinal γ>αs less than ω1β and a corresponded unique natural number n>max{njs∣j<is} so that γ matches the finite sequence {njs}j<is∪{n}. If during the search, we found an ordinal γ′ so that there is a number i′<is so that γ does not match {nj}j≤i′. Then do the action as in Case(1). In other words, let is+1 be the least such i′. Let αs+1=γ′ and claim j is active and njs+1 is undefined for all j≥is+1. Moreover, set njs+1=njs for any j<is+1. Go to next stage. Otherwise, by the construction of (x,f), there must be such γ and n. Find the least such γ and the corresponded n. Let αs+1=γ and is+1=is+1. Claim j is active and njs+1 is undefined for all j≥is+1. Moreover, set njs+1=njs for any j<is, niss+1=n and claim that is is inactive. Go to next stage.
This finishes the construction at stage s+1.
\bigskip
Let
θ=s∈ω⋃αs.
\begin{lemma}
For any i, there is some s so that for any t≥s, nit is defined, nit=nis and i is inactive at stage t for any t≥s.
\end{lemma}
\begin{proof}
Suppose not. Let i be the largest number (i could be 0) so that there is some s so that for any t≥s, nit is defined and nit=nis for any t≥s. Then there is an increasing sequence {sj}j∈ω so that isj=i+1 and sj>s for any j. Note that, by the construction, at stage sj+1, ni+1sj is defined and in the tree Tαsj+1β[x↾nisj+1,f↾nisj+1], (x↾ni+1sj+1,f↾ni+1sj+1) turns to right at most twice. In other words, there are at most two numbers l0<l1∈(nisj+1,ni+1sj+1) so that both (x↾l0,f↾l0) and (x↾l1,f↾l1) are splitting nodes in Tαsj+1β[x↾nisj+1,f↾nisj+1] such that x≻x↾l0⌢1 and x≻x↾l1⌢1. Moreover, l1 is the largest number less than ni+1sj+1 so that (x↾l1,f↾l1) is a splitting node in Tαsj+1β[x↾nisj,f↾nisj]. Since i+1 is activated at sj+1, αsj does not match {nksj+1}k≤i+1. Then either (x↾l1,f↾l1) is not a splitting node in Tαsj+1β[x↾nisj+1,f↾nisj+1] or there exists some d∈Φx↾ni+1sj+1 such that Lω1β⊨∀v∈Lαsj¬φi(f(d),v,β) but Lω1β⊨∃v∈Lαsj+1φi(f(d),v,β). In either case, the finite string (x↾l1⌢0,τ) will be cut off from Tαsj+1β[x↾nisj+1,f↾nisj+1]. But this happens for every j, so it is clear that (x,f) must be the leftmost infinite path in Tθβ[x↾k,f↾k] for some fixed k≥nis. Then (x,f) is the leftmost infinite path in Tω1ββ[x↾k,f↾k], which contradicts our construction of (x,f) (since y(i)=1 for infinitely many i's).
\end{proof}
\begin{lemma}
For any i, there must be some s and d∈Dom(Φx↾ni+1s) so that for any t≥s, either Lω1β⊨∀u<β∃v∈Lαsφi(u,v,β) or Lω1β⊨∀v∈Lαt¬φi(f(d),v,β)
\end{lemma}
\begin{proof}
By Lemma ?, there is some s so that for any t≥s, nit is defined, nit=nis and i is inactive at stage t for any t≥s. Then at stage s, either Lω1β⊨∀u<β∃v∈Lαsφi(u,v,β) or there is some d∈Dom(Φx↾ni+1s) such that Lω1β⊨∀v∈Lαs¬φi(f(d),v,β). If the first case happens, then we finishes the proof. Otherwise, since i is never activated from stage s and Dom(Φx↾ni+1s) is finite, there must be some fixed d∈Dom(Φx↾ni+1s) so that Lω1β⊨∀v∈Lαt¬φi(f(d),v,β).
\end{proof}
Remark: This argument can pushed up to prove Friedman's conjecture for Δ31-sets and answer several questions in 26 for level 3. Then by recent work of Yizheng Zhu, we believe those questions can be answered fully.
\part{Model theory and definability}
21. Descriptions in second order logic
The following is a result of Hyttinen, Kangas and V\"a\"an\"anen \cite[Thm. 3.3]{Hyttinen.etal:13}. It shows that under the right hypothesis on a cardinal κ, the models of a countable complete theory that have size κ can be described in second order logic iff the theory is easy in the sense of Shelah's main gap.
\begin{thm}[24] Let T be a countable complete theory. For every infinite cardinal κ with κ=ℵα, where ℶ(∣α∣+ω1)<κ and 2λ<2κ for each λ<κ, the following are equivalent:
\bi \item[(i)] Every model of T of size κ has a description in Lκ,ω2(T).
\item[(ii)] T is superstable, shallow, fails the dimensional order property DOP and fails the omitting types order property OTOP.
\ei
\end{thm}
Explanations:
Lκ,ω2(T) is the second-order language over the symbol set of T with disjunctions of size <κ and finite strings of quantifiers.
Superstability of T is stronger than stability: no infinite linear order can be defined in a model of T using a formula in Lω1,ω with parameters. Shelah proved that a model of a theory T without DOP can be thought of as built from a tree of small models. Shallowness of T means that for each model of T, this tree has no infinite path.
22. Kolezhitskiy: Robinson's theorem that $\ZZ$ is definable in $\QQ$
Yan Kolezhitskiy and Andr\'e Nies discussed a celebrated result of Julia Robinson as part of a semester reading project. The result was originally obtained as part of her 1948 PhD thesis under the supervision of Alfred Tarski. It then appeared in the 1949 J.Symb.\ Logic~39. Much simpler formulas for defining Z in Q have been obtained in subsequent work: a Π2 by Poonen, and recently a Π1 by Jochen Koenigsmann. If Z was also Σ1 definable in Q then the existential theory of Q would be undecidable, which is an open problem at present.
\begin{theorem}[39] The set of integers is definable without parameters in the field of rationals (Q,+,×,0,1). \end{theorem}
Idea and structure of the proof
A subset S of Q is called inductive if 0∈S and y∈S→y+1∈S for each y. The following is a monadic second-order definition of N in Q:
k∈N⇔∀S[S is inductive →k∈S].
Julia's idea was that it suffices to quantify over a small collection of sets S, which is uniformly parameterised by pairs of rationals a,b. Let
ϕ(a,b,k)≡∃x∃y∃z(2+abk2+bz2=x2+ay2)
She used some number theory to show that the sets Sa,b of the form {k:Q⊨ϕ(a,b,k)} suffice.
We can now turn the universal second-order quantification over S into a universal quantification over rationals a,b in order to obtain a first-order definition replacing (Eq. 3):
k∈N⇔∀a∀b[Sa,b is inductive →k∈Sa,b].
Clearly, with a smaller collection of sets S the implication from left to right in (Eq. 5) still holds. The worry is that we don't have enough sets any longer to separate a rational not in N from N. (We note that Julia actually only manages to separate non-integer rationals from N; a small complication of to the idea outlined above will be needed for that. She in effect first defines a set V in between N and Z, then notes that Z=V∪−V. )
We have to pick the condition ϕ(a,b,k) wisely, ensuring that the relevant sets Sa,b are inductive. This is done via the following fact. We say that k=n/din its lowest terms, if n∈Z, d∈N−{0} and (n,d)=1. We also say that d is the denominator of k in its lowest terms.
\begin{fact} Let S be a set of rationals given by a condition that holds for 0 and only depends on the denominator of the rational in lowest terms. Then S is inductive. \end{fact}
The fact
is evident because a rational q has the same denominator in lowest terms as q+1.
Next she shows that for two particular kinds of choices for a,b, the condition ϕ(a,b,k) in (Eq. 4) only depends on the denominator of k in its lowest terms. Firstly, b is a prime p such that p≡3mod4, and a=1.
\begin{lemma}
Suppose that p is a prime such that p≡3mod4. The equation 2+pk2+pz2=x2+y2 has a solution for x,y, and z iff the denominator of k in its lowest terms is odd, and is co-prime to p.
\end{lemma}
Secondly, a is a prime q and b is a prime p, with some additional restrictions. Recall that the Legendre ``symbol'' (k/p) is a binary function that returns 1 if k is a quadratic residue modp, 0 if k=0, and −1 otherwise.
\begin{lemma}
Suppose that p and q are odd primes such that p≡1mod4 and (q/p)=−1. The equation 2+pqk2+pz2=x2+qy2 has a solution for x, y, and z iff the denominator of k in its lowest terms is co-prime to both q and p.
\end{lemma}
Given these two lemmas, the proof concludes as follows. First one needs a number theoretic claim which provides the q we need in Lemma~ ?.
\begin{claim}
Suppose p is a prime such that p≡1mod4. There exists an odd prime q such that (q/p)=−1.
\end{claim}
\begin{proof} Let s be any (quadratic) non-residue mod p. Then s+p is also a non-residue. One of s, s+p is odd, say the former. There is an (odd) prime factor of s which is also a non-residue, because the Legendre symbol is multiplicative. Let this prime factor be q. \end{proof}
Let ψ(k) be a first-order formula expressing the right hand side of (Eq. 5). Clearly k∈N⇒ψ(k). We verify that ψ(k)⇒k∈Z. Suppose that k∈Q and ψ(k) holds. Write k=n/d in lowest terms. By Lemma~ ?, d is odd and not divisible by any prime p such that p≡3mod4. By Lemma~ ? using Claim~ ?, d not divisible by any prime p such that p≡1mod4. Therefore d=1.
Thus, k∈N⇒ψ(k)⇒k∈Z, so the formula ψ(k)∨ψ(−k) provides a first-order definition of Z in Q.
Proofs of Lemmas~?}
Julia relies on two claims that follow from the Hasse-Minkowski theorem.
\begin{claim}
Suppose p is a prime such that p≡3mod4. We have x2+y2−pz2=m for some m∈Q,m=0, iff it is not the case that
\indent\indent a) m=pks2, where (k/p)=1, or \\
\indent\indent b) m=ks2 with k≡p(mod8)\\\\
\end{claim}
\begin{claim}
Suppose p and q are odd primes such that p≡1mod4 and (q/p)=−1. There is some non-zero m∈Q such that x2+qy2−pz2=m, iff it is not the case that:\\
\indent\indent a) m=pks2 and (k/p)=−1\\
\indent\indent b) m=qks2 and (k/q)=−1\\\\
\end{claim}
\iffalse
\begin{proof}[Proof of {Lemma ?}]
We note that this lemma is equivalent to the following statement: Given a prime p, p≡3(mod4), for all M∈Q there exist X,Y, Z∈Q such that 2+pM2+pZ2=X2+Y2 iff the denominator of M, d is such that 2∤d and d is co-prime to p.\\
To prove this, we take some prime p that satisfies the antecedent, then we take an arbitrary M and write it as n/d, where d is the lowest denominator of M. We define m to be 2d2+pn2. Without loss of generality we consider 3 cases.\\\\
\noindent Case 1: 2∤d and d is co-prime to p:\\
\noindent Claim A: m is co-prime to p.
\noindent We show this by contradiction: suppose there exists some x, x=1 such that x∣m and x∣p. Since p is a prime, we have it that x=p. So p∣(2d2+pn2). Thus it must be the case that p∣2d2. This is only the case if p∣2 or p∣d. But by previous assumptions both of these are false, ergo we get a contradiction. Thus the claim holds.\\
Thus it is not the case that m can be represented as pks2, for any k and s.\\\\
\noindent Claim B: m≡1 or m≡2(mod4).
\noindent Since 4∣m would imply that 4÷2d2 and 4÷pn2, which would only be true if n and d had a common divisor, by our initial assumptions that d is the lowest denominator ofM, we conclude that 4∤m.\
[PROVE 3∤m]\\
\noindent Claim C: m is not of the form ks2, where k≡p(mod8):
\noindent [GIVE PROOF in modulo arithmetic] FROM Claim 1, and fact that p≡3(mod4)\\
From claims A and C, by Lemma 0.1, we get it that there exist X, Y, and Z such that m=X2+Y2−pZ2. In other words m can be represented by the given equation.\\\\
\noindent Case 2: p∣d.\\
We write d as pr. Then m=pk, where k=2pr2+n2.
\noindent Claim D: k and p are co-prime:\\\\
\noindent Claim E: (k/p)=(n2/p)=1
\noindent From these, we get that m=pk=pk12=pkS2, where (k/p)=1, and thus by Lemma 0.1, we get it that m cannot be represented by the given quadratic form.\\\\\\
\noindent Case 3: 2∣d
\noindent We write d=2s, then m=8s2+pn2.
\noindent Claim F: mmodp(mod8)
\noindent Since n is odd...\\\\
Thus, by claim F and ?, we have it that m is not represented by the said equation.\\
So from cases 1, 2, and 3, we draw the conclusion that m is represented by X2+Y2−pZ2 if 2∤d and d is co-prime to p.\\
We then note that by basic algebraic rearrangements, from this, we get:\\
2+pM2+p(dZ)2=(dX)2+(dY)2\\
\end{proof}
\fi
\def\cprime{′} \def\cprime{′}
References
Uri Andrews, Mingzhong Cai, David Diamondstone, Carl Jockusch, and Steffen Lempp.. Asymptotic density, computable traceability, and 1-randomness. Preprint, 2013.
L. Bienvenu, P. G\'acs, M. Hoyrup, C. Rojas, and A. Shen. Algorithmic tests and randomness with respect to a class of measures.. Proceedings of the Steklov Institute of Mathematics, 274(1):34--89, 2011. Published in Russian in \it Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2011, Vol. 274, pp. 41--102.
L. Bienvenu, N. Greenberg, A. Ku\vcera, A. Nies, and D. Turetsky. Coherent randomness tests and computing the K-trivial sets.. To appear in J. European Math. Society, 2016.
Andreas Blass. Some questions arising from hindman's theorem.. Scientiae Mathematicae Japonicae, (62):331--334, 2005.
J. Brendle, A. Brooke-Taylor, Keng Meng Ng, and A. Nies. An analogy between cardinal characteristics and highness properties. of oracles. In Proceedings of the 13th Asian Logic Conference: Guangzhou, China, pages 1--28. World Scientific, 2013. http://arxiv.org/abs/1404.2839.
Yue Yang Chi Tat Chong, Steffen Lempp. On the role of the collection principle for $\sigma^0_2$ formulas in. second-order reverse mathematics. Proceedings of the American Mathematical Society, 138:1093--1100, 2010.
Yue Yang Chi Tat Chong, Theodore Slaman. The metamathematics of the stable ramsey's theorem for pairs.. Journal of the American Mathematical Society, 27:863--892, 2014.
Barbara F Csima and Joseph R Mileti. The strength of the rainbow Ramsey theorem.. The Journal of Symbolic Logic, 74(04):1310--1324, 2009.
Jeff Hirst Damir Dzhafarov. The polarized ramsey's theorem.. Archive for Mathematical Logic, 48(2):141--157, 2009.
Reed Solomon Linda B. Westrick Damir Dzhafarov, Carl G. Jockusch. Effectiveness of hindman's theorem for bounded sums.. In N. Greenberg B. Khoussainov A. Melnikov A. Day, M. Fellows, editor, Proceedings of the International Symposium on Computability and Complexity (in honour of Rod Downey's 60th birthday), Lecture Notes in Computer Science. Springer, To appear.
A. Nies (editor). Logic Blog 2013.. Available at http://arxiv.org/abs/1403.5719, 2013.
A. Nies (editor). Logic Blog 2015.. Available at http://arxiv.org/abs/1602.04432, 2015.
S. Figueira, D. Hirschfeldt, J. Miller, Selwyn Ng, and A Nies. Counting the changes of random $\Delta^0_2$ sets.. J. Logic Computation, 25:1073--1089, 2015. Journal version of conference paper at CiE 2010.
Santiago Figueira, Joseph S. Miller, and Andr\'e Nies. Indifferent sets.. J. Logic Comput., 19(2):425--443, 2009.
M. Fried and M. Jarden. Field arithmetic, volume 11.. Springer Science \& Business Media, 2006.
Su Gao. Invariant descriptive set theory, volume 293 of Pure and. Applied Mathematics (Boca Raton). CRC Press, Boca Raton, FL, 2009.
Su Gao, S. Jackson, and B. Seward. Group colorings and Bernoulli subflows, volume 241.. American Mathematical Society, 2016.
D. Gorenstein, R. Lyons, and R. Solomon. The classification of the finite simple groups 3, volume 40.. American Mathematical Soc., 1998.
Alexandre Grothendieck. R\'esum\'e de la th\'eorie m\'etrique des produits tensoriels. topologiques. Resenhas do Instituto de Matem\'atica e Estat\'\istica da Universidade de S\ ao Paulo, 2(4):401--481, 1996. This is a reprint of a 1953 paper.
R. M. Guralnick, W. M. Kantor, M. Kassabov, and A. Lubotzky. Presentations of finite simple groups: a quantitative approach.. J. Amer. Math. Soc., 34:711--774, 2008.
Leo A. Harrington. Analytic determinacy and $0^\#$.. J. Symbolic Logic, 20:685--693, 1978.
M. Hoyrup and C. Rojas. Computability of probability measures and Martin-L\"of randomness. over metric spaces. Inform. and Comput., 207(7):830--847, 2009.
Mathieu Hoyrup and Cristobal Rojas. An Application of Martin-L\"of Randomness to Effective Probability. Theory. In Klaus Ambos-Spies, Benedikt L\"owe, and Wolfgang Merkle, editors, CiE, pages 260--269. Springer, 2009.
T. Hyttinen, K. Kangas, and J. V\"a\"an\"anen. On second-order characterizability.. Logic Journal of IGPL, 21(5):767--787, 2013.
M. Jarden and A. Lubotzky. Random normal subgroups of free profinite groups.. Journal of Group Theory, 2:213--224, 1999.
Alexander S. Kechris, Donald A. Martin, and Robert M. Solovay. Introduction to $Q$-theory.. In Ordinal Definability and Recursion Theory. The Cabal Seminar. Volume III, volume 43 of Lect. Notes Log., pages 126--199. Cambridge University Press, Cambridge, 2016.
Wolfgang Kimmerle, Richard Lyons, Robert Sandling, and David N Teague. Composition factors from the group ring and artin's theorem on orders. of simple groups. Proceedings of the London Mathematical Society, 3(1):89--122, 1990.
Donald A. Martin. Proof of a conjecture of Friedman.. Proc. Amer. Math. Soc., 55(1):129, 1976.
B. Monin and A. Nies. A unifying approach to the Gamma question.. In Proceedings of Logic in Computer Science (LICS). IEEE press, 2015.
A. Nies. Calculus of cost functions.. To appear in Barry Cooper and Mariya Soskova (eds.), The Incomputable: Journeys beyond the Turing barrier, Springer-Verlag.
A. Nies. Computability and randomness, volume 51 of Oxford Logic. Guides. Oxford University Press, Oxford, 2009. 444 pages. Paperback version 2011.
A. Nies and K. Tent. Describing finite groups by short first-order sentences.. Israel J. of Mathematics, to appear, 2014, updated 2015. available at arXiv:1409.8390.
Theodore A. Slaman Peter A. Cholak, Carl G. Jockusch. On the strength of ramsey's theorem for pairs.. Journal of Symbolic Logic, 66(1):1--55, 2001.
G. Pisier. Grothendieck’s theorem, past and present.. Bulletin of the American Mathematical Society, 49(2):237--323, 2012.
Michael O. Rabin. Computable algebra, general theory and theory of computable fields.. Trans. Amer. Math. Soc., 95:341--360, 1960.
P. Raghavendra and D. Steurer. Towards computing the grothendieck constant.. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 525--534. Society for Industrial and Applied Mathematics, 2009.
L. Ribes and P. Zalesskii. Profinite groups.. Springer, 2000.
D. Robinson. A course in the theory of groups.. Springer--Verlag, 1988.
J. Robinson. Definability and decision problems in arithmetic.. J. Symbolic Logic, 14(2):98--114, 1949.
S. G. Simpson. Subsystems of second order arithmetic.. Perspectives in Logic. Cambridge University Press, Cambridge, second edition, 2009.
R. Smith. Effective aspects of profinite groups.. The Journal of Symbolic Logic, 46(04):851--863, 1981.
S. Thomas. Topological full groups of minimal subshifts and just-infinite. groups. In Proceedings of the 12th Asian Logic Conference, pages 298--313. World Scientific, 2013.
Ingo Wegener et al. The complexity of Boolean functions, volume 1.. BG Teubner Stuttgart, 1987.
Liang Yu. A new proof of Friedman's conjecture.. Bull. Symbolic Logic, 17(3):455--461, 2011. \endthebibliography